在無序列表中查找缺少的數字

我在下面編寫了一個示例代碼，以在無序列表中找到缺少的數字。例如{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

在無序列表中查找缺少的數字

回答

相關問題