Поиск отсутствующих целых чисел в отсортированном массиве

Question

Мне пришлось найти недостающие целые числа (случайным образом сгенерированные в диапазоне от 0 до 9) в массиве с длиной = 10. У меня возникла идея отсортировать массив и затем проверить каждый массив если он равен позиции в массиве. Я придумал следующий код:

public void nichtGetroffen(){ 
    s.quickSort(enten, 0, enten.length -1); 
    sum = 0; 
    for (int i=0; i < enten.length; i++){ 
     if(enten[i] != i){ 
      System.out.print(i + ""); 
      sum = sum +1; 
     } 
    } 

Проблемы заключается в том, что она иногда работает, а иногда нет, и я, к сожалению, не имею представления о том, как решить эту проблему. (enten - это имя массива)

Answer 1

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

s.quickSort(enten, 0, enten.length -1); 

// Print missing numbers less than the smallest element. 
for (int j = 0; j < enten[0]; ++j) { 
    System.out.println(j); 
} 

// Print missing numbers between elements. 
for (int i = 1; i < enten.length; ++i) { 
    // If enten[i - 1] + 1 >= enten[i], this loop body never runs. 
    for (int j = enten[i - 1] + 1; j < enten[i]; ++j) { 
    System.out.println(j); 
    } 
} 

// Print missing numbers greater than the largest element. 
for (int j = enten[enten.length-1] + 1; j <= 9; ++j) { 
    System.out.println(j); 
} 

Answer 2

Если бы я сделал understend хорошо ваш вопрос, заполнить set коллекцию массива вы получили, а затем проверьте длина является равна 10.

HashSet<Integer> set = new HashSet<>(arrayOfRandomNumbers); 
if (set.size() == 10) { 
    //all elements in array 
} 

Answer 3

Один из способов сделать это так использовать Set и его свойство иметь уникальные элементы только:

public static void main(String[] args) { 
    // randomizing 
    int nMin = 5; 
    int nMax = 50; 
    int x = 20; 
    Random r = new Random(); 
    Integer[] arr = new Integer[x]; 
    for (int i = 0; i < x; i++) { 
     int val = nMin + r.nextInt(nMax - nMin); 
     System.out.println(val); 
     arr[i] = val; 
    } 

    // detection 

    Set<Integer> set = new HashSet<Integer>(Arrays.asList(arr)); 
    List<Integer> missing = new ArrayList<>(); 
    for (int i = nMin; i < nMax; i++) { 
     if (!set.contains(i)) { 
      missing.add(i); 
     } 
    } 

    System.out.println("Missing elements count " + missing.size()); 
    System.out.println("Missing elements: " + missing.toString()); 
} 

Это даст вам все недостающее interegs из множества X (20) случайных чисел между Nmin (5) и nMax (50) включительно;

Answer 4

Вот полное решение вашей «первоначальная задача» вы упомянули в комментарии:

public class Gaps { 
    public static void main(String[] args) { 
     int runs = 100; 
     int nMin = 0; 
     int nMax = 10; 
     int x = 10; 

     double missingSum = 0; 

     for (int run = 0; run < runs; run++) { 
      Integer[] arr = randomize(nMin, nMax, x); 
      List<Integer> missing = getMissingElements(nMin, nMax, arr); 
      missingSum += missing.size(); 
     } 
     double avg = missingSum/runs; 
     System.out.println("Missing elements avarage count: " + avg); 

    } 

    private static List<Integer> getMissingElements(int nMin, int nMax, Integer[] arr) { 
     Set<Integer> set = new HashSet<Integer>(Arrays.asList(arr)); 
     List<Integer> missing = new ArrayList<>(); 
     for (int i = nMin; i < nMax; i++) { 
      if (!set.contains(i)) { 
       missing.add(i); 
      } 
     } 
     return missing; 
    } 

    private static Integer[] randomize(int nMin, int nMax, int x) { 
     Random r = new Random(); 
     Integer[] arr = new Integer[x]; 
     for (int i = 0; i < x; i++) { 
      int val = nMin + r.nextInt(nMax - nMin); 
      arr[i] = val; 
     } 
     return arr; 
    } 

} 

Answer 5

Вот пример того, почему он не работает:

Говорит, что отсортированный массив содержит следующие номера: 1 2 3 4 5 6 7 8 9 9. Сколько чисел в этом массиве отсутствует? Единственный. Нам не хватает номера 0.

Сколько номеров находится в их «правильном» месте? Только последние 9. Вот почему ваш код вернет 9 вместо 1.