Dämonplay Dämonplay - 2 months ago 11
Java Question

Finding missing integers in a sorted array

I had to find the missing integers (randomly generated in the range of 0-9) in an array with length = 10. I had the idea to sort the array and then check for each array if it equals the position in the array. I came up with the following code:

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;
}
}


The problem is that it works sometimes and sometimes it doesn't and I unfortunately don't have an idea how to solve this. (enten is the name of the array)

Answer

If you sort the array, if the next element is more than 1 greater than the current element, you've got missing numbers. Then, just look for missing numbers at the start and end of the array.

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);
}
Comments