Поиск недостающего номера в неупорядоченном списке

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), чтобы проверить наличие чисел в наборе.

Answer 2

Поместите целые числа в 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, чтобы указать, что не будет никаких повторяющихся элементов, что имеет смысл в этом контексте, потому что число не может отсутствовать более одного раза.