在无序列表中查找缺少的数字

我在下面编写了一个示例代码，以在无序列表中找到缺少的数字。例如{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; 
}

来源

2015-12-02 Jayesh

定义_missing_。那么0呢？那6点呢？那么24123123呢？这是一个范围吗？ –

你知道列表的范围吗？ – jpganz18

在你的代码中，如果第一个数字是0，其余的都是坏的。 – jpganz18

从丢失号码是没有在numbers发现1..max数字代码假设。

该代码将起作用，但可以进行改进：当您只需维护一组没有与其关联的值的项目时，可以使用HashSet而不是HashMap。然后你做set.add(num)，但你可以用new HashSet<>(numbers)来构造它，而不是逐个添加项目。然后使用set.contains(i)检查集合中的号码存在。

来源

2015-12-02 23:06:08 hotkey

谢谢。这有助于。我完全忘记了HashSets。 :) – Jayesh

把整数变成TreeSet。 Set.contains()可让您有效检查其是否包含给定的编号，并且SortedSet.last()可让您有效地确定其最大元素。然后用IntStream.rangeClosed()迭代您的范围，过滤掉您的集合中包含的每个元素，并收集剩下的内容返回给调用者。

import static java.util.stream.Collectors.toCollection; 
import static java.util.stream.IntStream.rangeClosed; 

import java.util.Collection; 
import java.util.Set; 
import java.util.SortedSet; 
import java.util.TreeSet; 

Set<Integer> missing(Collection<Integer> collection) { 
    SortedSet<Integer> set = new TreeSet<>(collection); 
    return rangeClosed(1, set.last()).boxed() 
            .filter(i -> !set.contains(i)) 
            .collect(toCollection(TreeSet::new)); 
}

我变得更加普遍被接受Collection代替List因为List意味着秩序，你说的是不重要的。我返回一个Set来表示不会有任何重复元素，这在这种情况下是有意义的，因为一个数字不能多于一次地丢失。

来源

2015-12-02 23:42:00 gdejohn

在无序列表中查找缺少的数字

回答

相关问题