java - 在无序列表中查找缺失的数字

Question

我在下面编写了一个示例代码来查找无序列表中丢失的数字。例如 {5,2,3} 应返回 {1,4}。我的问题是，使用HashMap进行快速查找是否正确？范围是 1 和输入列表中的最大数字。

public List<Integer> findMissing(List<Integer> numbers) {
        int max = 0;
        List<Integer> result = new ArrayList<Integer>();
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();

        for(Integer num : numbers) {
          if(num > max) 
              max=num;
          map.put(num,num);   
        }  

        int missingCount=max-numbers.size();

        for(int i=1;i<=max;i++) {
               if(missingCount == 0) break;

               if(!map.containsKey(i)) {
                   result.add(i);
                   missingCount--;
               }

        }
        return result;
}

Answer 1

从代码中假设缺失的数字是 1..max 中的数字在 numbers 中找不到.

代码可以工作，但可以改进:HashSet可以用来代替 HashMap当您只需要维护一组没有关联值的项目时。然后你就做set.add(num) ，但你可以用 new HashSet<>(numbers) 来构造它而不是一项一项地添加项目。然后使用set.contains(i)检查集合中是否存在数字。