Поиск недостающих чисел из массива

Question

Написал этот код, хотел бы получить лучший подход, используя любой алгоритм для поиска недостающих чисел из отсортированного или несортированного массива. Если его несортированный массив, я бы сортировал и выполнял следующее.

private static void identifyMissingValues(Integer[] ar) { 

     for(int i = 0; i < (ar.length - 1); i++) { 

      int next = ar[i + 1]; 
      int current = ar[i]; 
      if((next - current) > 1) { 
       System.out.println("Missing Value : " + (current + 1)); 
      } 
     } 
    } 

Любой код быстрее или лучше этого, пожалуйста, предложите.

Answer 1

Могу ли я узнать количество входных и ожидаемых выходных номеров?
Согласно вашему коду, я чувствую, что серия должна быть разницей в 1, если я не ошибаюсь.

Answer 2

Итак, у вас есть массив из n элементов, который начинается с целого числа i и содержит все целые числа от i до i + n, это так? Например:

arr = [1,2,3,4,5] 

Таким образом, сумма всех чисел в массиве должна быть суммой чисел от i до i + n.

Например: sum(arr) = 1+2+3+4+5 = 15

Формула для суммы чисел от 1 до п n(n+1)/2

Таким образом, вы можете иметь цикл как:

int counter = 0; 

for(Integer i : integers) 
    counter += i 

Чтобы получить сумму чисел в ваш массив.

Если ваш массив начинается с одного, вы проверяете, является ли переменная counter равной n(n+1)/2, где n - это длина вашего массива.

Если ваш массив не начинается с одного, например arr = [78, 79, 80, 81], вам нужно немного подправить этот подход, но я уверен, что вы можете это понять.

Answer 3

Сортировка массива займет O(n*log(n)).

Вы можете сделать лучше, если вы добавите все элементы массива в HashSet(O(n)) времени выполнения, а затем проверить для каждого номера между 0 и ar.length - 1 (или любой другой соответствующий диапазон есть) HashSet, содержит ли это число. Это займет O(n) раз.

Answer 4

Вы можете сделать:

Set<Integer> mySet = new TreeSet<Integer>(Arrays.asList(ar)); 
int min = mySet.first(); 

for (int i = 0; i < mySet.size(); i++) { 
    int number = min + i; 
    if (!mySet.contains(number)) { 
     System.out.println ("Missing: " + number); 
     i--; 
    } 
} 

Answer 5

Любой код быстрее или лучше, чем это, пожалуйста, предложите.

Нет нет такой вещи, - вы не можете улучшить на O(n) алгоритма, если необходимо посетить каждый элемент.

Answer 6

Ваш подход хорош, но я добавил что-то большее для более чем одного номера.

eg : ar={1,2,4,6,10} // Sorted Array 

private static void identifyMissingValues(Integer[] ar) { 
    for (int i = 0; i < (ar.length - 1); i++) { 
     int next = ar[i + 1]; 
     int current = ar[i]; 
     if ((next - current) > 1) { 
      for (int ind = 1; ind < next - current; ind++) 
       System.out.println("Missing Value : " + (current + ind)); 
     } 
    } 
} 

Выход,

Missing Value : 3 
Missing Value : 5 
Missing Value : 7 
Missing Value : 8 
Missing Value : 9 

Answer 7

Integer [] list = new Integer[]{1, 12, 85, 6, 10}; 


Integer previous = null; 


Arrays.sort(list); 

System.out.println(list); 


for(int index = 0; index < list.length; index++){ 


    if(previous == null){ 
     previous = (Integer) list[index]; 
     continue; 
    } 

    Integer next = previous + 1; 
    if(((Integer) list[index] - previous) > 1){ 

     System.out.println("Missing value " + next); 
     index--; 

    } 
    previous = next; 


} 

Answer 8

Использование BitSet вместо сортировки.

int[] ar = {7, 2, 6, 8, 10, 4, 3, 2}; 
    int min = IntStream.of(ar).min().getAsInt(); 
    BitSet b = new BitSet(); 
    for (int i : ar) 
     b.set(i - min); 
    int i = 0; 
    while ((i = b.nextClearBit(i + 1)) < b.length()) 
     System.out.println(i + min); 

результат

5 
9