Узнайте n номеров отсутствующих элементов из массива в Java

У меня есть массив, который несет некоторые целые числа. Скажем, numbers={3,0,1} или, скажем, numbers={9,6,4,2,3,5,7,0,1}. Теперь я должен выяснить пропущенные числа из массива. Согласно этому примеру в каждом наборе есть только одно пропущенное число. 1-й промах 2 и 2-й промах 8.

Я уже написал это. Мой код не только обнаруживает одно пропущенное число из указанного набора, но также может найти более 1 пропущенного числа из заданного набора.

Но если два последовательных числа отсутствуют в одном наборе, это не может быть обнаружено.

My code
import java.util.Arrays;

public class Missing_number 
{
    public static void main( String args[] )
    {
        int numbers[]={9,6,4,5,7,0,1};
        Arrays.sort(numbers);
        int i=1;

        while ( i < numbers.length ) 
        {
            if ( numbers[i] - numbers[i-1] == 1 ) 
            {
            } 
            else 
            {
                System.out.println( "Missing number is " + ( numbers[i-1] + 1 ) );
            }
            i++;
        }
    }
}

Я так думаю, если мне удастся добавить 1-е недостающее число в массив, а затем начать поиск, как будет выглядеть код? numbers={9,6,4,5,7,0,1} Теперь 8 уже отсутствуют в этом наборе. Теперь я исключил еще два элемента (2,3) из списка. Вывод: согласно моему коду: 2,8 Но 3 также отсутствует, но это не отображается.

Я думаю, что если я смогу добавить 2 в массив чисел, то это может быть немного проще. Но, как мы все знаем, массив Java является неизменным, поэтому мы не можем увеличить его длину.

Так что, возможно, я буду использовать список. Но в списке этот тип индексации number[0]=something не поддерживается. Так, как я мог продолжить тогда. Я использую список или все еще застрял в массиве?

Поэтому я предпринимаю попытку создать его с помощью arraylist.

Mycode(modified version from array)

 public class T1 {
 public static void main(String args[]){
    List<Integer> numbers=new ArrayList<>();
    numbers.add(9);
    numbers.add(6);
    numbers.add(4);
    numbers.add(5);
    numbers.add(7);
    numbers.add(0);
    numbers.add(1);
    Collections.sort(numbers);
    int i=1;
    while(i< numbers.size()) {
        if (numbers.get(i) - numbers.get(i-1) == 1) {

        } else {
            System.out.println("Missing number is " + (numbers.get(i-1) + 1));
            numbers.add((numbers.get(i-1)+1));
            Collections.sort(numbers);
        }
        i++;
    }

    }
}

Arraylist может решить мою проблему. Но есть ли вероятность, что простой массив может решить эту проблему?

Ответ 1

Этот код использует HashSet:

public static void main(String[] args) {
    int[] numbers = {9, 6, 4, 5, 7, 0, 1};
    Arrays.sort(numbers);
    HashSet<Integer> set = new HashSet<>();

    for (int i = numbers[0]; i < numbers[numbers.length - 1]; i++) {
        set.add(i);
    }

    for (int i = 0; i < numbers.length; i++) {
        set.remove(numbers[i]);
    }

    for (int x : set) {
        System.out.print(x + " ");
    }
}

напечатает:

2 3 8

Вот как это работает:
1. Добавляет все числа от минимального номера массива до максимального номера массива в наборе.
2. Перебирает массив и удаляет каждый элемент массива из набора.
3. Распечатывает оставшиеся элементы в наборе, которые являются всеми недостающими элементами массива.

Ответ 2

заменить условие else на:

for(int j=numbers[i-1] + 1; j <= numbers[i] - 1; j++) {
    System.out.println( "Missing number is " + ( j ) );
}

давайте рассмотрим случай: {9, 6, 4, 5, 7, 0, 1} после сортировки будет: {0, 1, 4, 5, 6, 7, 9} теперь, если i по индексу 2, он находит разница между numbers[i] и numbers[i-1] не равна 1 (4 - 1 = 3), теперь вам нужны ВСЕ числа от 1 до 4, которые равны 2, 3, и, следовательно, вы должны зацикливаться на numbers[i-1] на numbers[i] (эксклюзив) для достижения этой цели.

Сложность этого кода большая O из N (O(N)), где N является самым большим элементом в вашем массиве.

Ответ 3

Есть много вопросов, которые остались без ответа здесь. Например, всегда ли массив начинается с нуля? Какой максимальный размер? и т.п.

Вот простой способ решения этой проблемы,

Найдите максимальное количество в вашем наборе.
Создайте пустой boolean массив длины, равной максимальному числу, найденному на последнем шаге, плюс единица.
Отсканируйте исходный набор и установите значение вашего нового логического массива с индексом, равным числу в вашем исходном наборе, равным true.
Наконец просканируйте ваш boolean массив, чтобы найти и распечатать все индексы со значением false.

Пример:

Оригинальный набор: {1,0,3}

Шаг 1: Максимальное количество в наборе = 3
Шаг 2: логический массив с длиной = 3 + 1 → {ложь, ложь, ложь, ложь}
Шаг 3: при сканировании исходного набора и значений настроек в boolean массиве это будет конечное состояние → {true, true, false, true}
Шаг 4: Наконец, вы просканируете boolean массив для печати 2, так как это только индекс, значение которого равно false

Ответ 4

int[] numbers = { 11, 6, 4, 5, 7, 1 };
Arrays.sort(numbers);
int numbersArrayIndex = 0;
for (int i = 0; i < numbers[numbers.length - 1]; i++) {
    if (i == numbers[numbersArrayIndex]) {
        numbersArrayIndex++;
    }
    else {
        System.out.println(i);
    }
}

Ответ 5

        int[] a= {0,12,14,15,32};
        Arrays.sort(a);
        for(int i=0;i<a.length-1;i++)
        {
            if(a[i+1]-a[i]>1)
            {
                int temp=a[i+1]-a[i];
                for(int j=1;j<temp;j++) 
                {
                 System.out.print(a[i]+j + " ");
                }
                temp=0;
            }
        }

Вывод: 1 2 3 4 5 6 7 8 9 10 11 13 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31