Производительность при поиске пропущенных чисел в массиве

Question

Данный список содержит все числа, кроме 2, от 1 до 20 (в случайном порядке). Мне нужно найти эти 2 числа.

Это (рабочая) программа, которую я придумал:

public static void main(String[] args) {
    int[] x= {1,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19};
    ArrayList al= new ArrayList();
    Map map= new HashMap();
    for(int i=0;i<x.length;i++)
    {
        map.put(x[i], x[i]);
    }
    for(int i=1;i<=20;i++)
    {
        if(map.get(i)==null)
            al.add(i);
    }
    for(int i=0;i<al.size();i++)
    {
        System.out.println(al.get(i));
    }
}

Хотелось бы узнать, хороша ли программа с точки зрения производительности (память и bigO (n))?

Answer 1

Вам не нужна карта. Просто дополнительный логический массив размером 20.

for (int i = 0; i < input.length; i++)
   arr[input[i]] = true;

for (int i = 1; i <= 20; i++)
   if (arr[i] == false) {
      //number `i` is missing
   }     

Теперь я покажу простое математическое решение.

Сначала сложите все числа в массиве. Например, у вас есть 5, 1, 4 для чисел от 1, 2, 3, 4, 5. Так что 2 и 3 отсутствуют. Мы можем легко найти их с помощью математики.

5 + 1 + 4 = 10
1 + 2 + 3 + 4 + 5 = 15

Итак, мы знаем x + y = 15 - 10 = 5 Теперь мы получим второе уравнение:

1 * 4 * 5 = 20
1 * 2 * 3 * 4 * 5 = 120
=> x * y = 120 / 20 = 6

Итак:

x + y = 5
x * y = 6

=> x = 2, y = 3 or x = 3, y = 2, что тоже самое.

Итак x = 2, y = 3

Answer 2

Другой вариант - использовать BitSet, где каждый бит установлен для соответствующего числа в массиве.

Answer 3

Не должно быть ничего хуже, чем линейное время O (n): один прогон для заполнения массива флагов и второй прогон для проверки массива флагов.

Answer 4

Ваш код работает на O (n) из-за операции map.put. Цикл for, приведенный ниже, будет работать в O (n) и в худшем случае, так что в целом вся ваша функция выполняется в O (n).

Вы можете оптимизировать свой код дальше. Например, вы используете дополнительную память. Чтобы улучшить это, вам нужно придумать 2 уравнения, чтобы вывести пропущенные числа x и y.

Eqn1: Суммирование (от 1 до 20) = n * (n + 1) / 2 Добавить все числа в массив и сохранить в темп. x + y = n * (n + 1) / 2 - temp

Eqn2: Умножьте (от 1 до 20) = n! Умножьте все числа в массиве и сохраните в темп. x * y = temp / n!

Решите уравнения, чтобы получить х и у.

Так что это запустит O (n) без большого количества памяти.