Как найти недостающие числа в последовательности

Учитывая массив n-1 различные целые числа в диапазоне от 1 до n, найти в нем пропущенное число за линейное время.

Например, рассмотрим массив {1, 2, 3, 4, 5, 7, 8, 9, 10} элементы которого различны и находятся в диапазоне от 1 до 10. Недостающее число — 6.

Потренируйтесь в этой проблеме

1. Использование формулы для суммы первых n Натуральные числа

Мы знаем, что сумма первых n натуральные числа можно вычислить по формуле 1 + 2 + … + n = n×(n+1)/2. Мы можем использовать эту формулу, чтобы найти пропущенное число.

Идея состоит в том, чтобы найти сумму целых чисел от 1 до n+1 используя приведенную выше формулу, где n размер массива. Также вычислите фактическую сумму целых чисел в массиве. Теперь недостающее число будет разницей между ними.

Этот подход демонстрируется ниже на C, Java и Python:

2. Использование оператора XOR

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

Идея состоит в том, чтобы вычислить XOR всех элементов массива и вычислить XOR всех элементов от 1 до n+1, куда n размер массива. Теперь недостающее число будет XOR между ними.

Этот подход демонстрируется ниже на C, Java и Python:

Временная сложность обоих рассмотренных выше методов составляет O(n) и не требует дополнительного места, где n это размер ввода.

If the input sequence is sorted, you could use sets here. Take the start and end values from the input list:

def missing_elements(L):
    start, end = L[0], L[-1]
    return sorted(set(range(start, end + 1)).difference(L))

This assumes Python 3; for Python 2, use xrange() to avoid building a list first.

The sorted() call is optional; without it a set() is returned of the missing values, with it you get a sorted list.

Demo:

>>> L = [10,11,13,14,15,16,17,18,20]
>>> missing_elements(L)
[12, 19]

Another approach is by detecting gaps between subsequent numbers; using an older itertools library sliding window recipe:

from itertools import islice, chain

def window(seq, n=2):
    "Returns a sliding window (of width n) over data from the iterable"
    "   s -> (s0,s1,...s[n-1]), (s1,s2,...,sn), ...                   "
    it = iter(seq)
    result = tuple(islice(it, n))
    if len(result) == n:
        yield result    
    for elem in it:
        result = result[1:] + (elem,)
        yield result

def missing_elements(L):
    missing = chain.from_iterable(range(x + 1, y) for x, y in window(L) if (y - x) > 1)
    return list(missing)

This is a pure O(n) operation, and if you know the number of missing items, you can make sure it only produces those and then stops:

def missing_elements(L, count):
    missing = chain.from_iterable(range(x + 1, y) for x, y in window(L) if (y - x) > 1)
    return list(islice(missing, 0, count))

This will handle larger gaps too; if you are missing 2 items at 11 and 12, it’ll still work:

>>> missing_elements([10, 13, 14, 15], 2)
[11, 12]

and the above sample only had to iterate over [10, 13] to figure this out.

Предположим, у вас есть длинный список порядковых номеров для маркировки элементов, таких как номера чеков в банковских выписках, обычно мы прокручиваем и находим недостающие порядковые номера вручную. Иногда это довольно сложно и требует много времени. Вы можете придумать хитрые способы справиться с этим. Да, есть несколько простых способов быстро и удобно определить и найти последовательность отсутствующих чисел в Excel 2007, Excel 2010 и Excel 2013.

Определите последовательность отсутствующих чисел с помощью формулы ЕСЛИ

Определите последовательность отсутствующих чисел с помощью формулы массива

Определите последовательность пропущенных чисел с помощью Kutools for Excel быстро

Определите последовательность отсутствующих чисел с помощью формулы ЕСЛИ

Как мы все знаем, большинство порядковых номеров имеют фиксированное приращение 1, например, 1, 2, 3,…, N. Следовательно, если вы можете определить, что число не меньше 1, чем его следующее число, это означает, что число отсутствует. .

Мы покажем вам руководства с примером, как показано на следующем скриншоте:

1. В пустой ячейке введите формулу = ЕСЛИ (A3-A2 = 1; «»; «Отсутствует»), и нажмите Enter ключ. В этом случае мы вводим формулу в ячейку B2.

Если нет пропущенных чисел, эта формула ничего не вернет; если пропущенные числа существуют, он вернет текст «Отсутствует» в активной ячейке.

2. Выберите ячейку B2 и перетащите маркер заполнения над диапазоном ячеек, который вы хотите содержать эту формулу. Теперь он идентифицирует отсутствующие числа с текстом «Отсутствует» в соответствующих ячейках столбца B. См. Следующий снимок экрана:

Определите последовательность отсутствующих чисел с помощью формулы массива

Иногда требуется не только определить последовательность отсутствующих номеров, но и перечислить отсутствующие номера. Вы можете справиться с этим, выполнив следующие шаги:

1. в соседней ячейке введите формулу = SMALL(IF(ISNA(MATCH(ROW(A$1:A$30),A$1:A$30,0)),ROW(A$1:A$30)),ROW(A1))

A1: A30 = диапазон чисел, последовательность для проверки от 1 до 30

2. нажмите Shift + Ctrl + Enter Ключи вместе, чтобы закончить формулу. Скопируйте формулу, пока не получите # ЧИСЛО! ошибки, означающие, что были перечислены все отсутствующие числа. Смотрите скриншот:

Определите последовательность пропущенных чисел с помощью Kutools for Excel быстро

Вышеупомянутые методы могут идентифицировать только отсутствующую чистую числовую последовательность, если у вас есть такая последовательность, как AA-1001-BB, AA-1002-BB, они могут не работать успешно. Но не волнуйся, Kutools for Excelмощная функция — Найти отсутствующий порядковый номер может помочь вам быстро определить недостающую последовательность.

Примечание:Чтобы применить это Найти отсутствующий порядковый номер, во-первых, вы должны скачать Kutools for Excel, а затем быстро и легко примените эту функцию.

После установки Kutools for Excel, пожалуйста, сделайте так:

1. Выберите последовательность данных, в которой вы хотите найти недостающую последовательность.

2. Нажмите Кутулс > Вставить > Найти отсутствующий порядковый номер, см. снимок экрана:

3. в Найти отсутствующий порядковый номер диалоговое окно:

(1.) Если вы выберете Вставка нового столбца со следующим отсутствующим маркером вариант, все недостающие порядковые номера отмечены текстом Отсутствующий в новом столбце рядом с вашими данными. Смотрите скриншот:

(2.) Если вы выберете Вставка отсутствующего порядкового номера вариант, все недостающие числа были вставлены в список последовательностей. Смотрите скриншот:

(3.) Если вы выберете Вставка пустых строк при включении отсутствующих порядковых номеров вариант, все пустые строки вставляются, когда отсутствуют числа. Смотрите скриншот:

(4.) Если вы выберете Цвет заливки фона вариант, расположение недостающих номеров будет выделено сразу. Смотрите скриншот:

Определите последовательность пропущенных чисел с помощью Kutools for Excel быстро

Далее представлен калькулятор, при помощи которого можно искать пропущенные номера в последовательности целых чисел. Пример такой последовательности (каждое число на новой строке):

1
2
3
4
6
7
12
13
18
Как видно в последовательности есть пропуски и единичных номеров и нескольких подряд следующих номеров. Например, номер 5 пропущен, а также пропущено два куска: между 8 и 11 и между 14 и 17.

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

Настройки калькулятора пропусков

Для более сложных случаев имеется несколько настроек:

• Установите флажек «В сжатом виде» чтобы калькулятор выдавал диапазоны последовательных пропусков номеров, например 8 — 11, где 8 начало, а 11 конец последовательного пропуска. В противном случае будет выдана вся последовательность пропущенных номеров, например 8, 9, 10, 11.
• Можно установить галочку «Использовать регулярные выражения для выделения номеров», для выделения чисел из строки при помощи регулярного выражения.

Последняя опция становится актуальной, если в вашем перечне номеров содержатся не только числа, например вот такая последовательность:
1 Бумага побеждает камень
2 Ножницы режут бумагу
3 Камень разрушает ножницы

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

недавно у меня был подобный (не точно такой же) вопрос на собеседовании, а также я слышал от друга, который был задан точно такой же вопрос в интервью.
Итак, вот ответ на вопрос OP и еще несколько вариантов, которые могут быть потенциально заданы.
Пример ответов приведен в Java, потому что, он заявил, что:

решение Java предпочтительнее.

решение 1:

массив чисел от 1 до 100 (включительно) … Числа случайным образом добавляются в массив, но есть один случайный пустой слот в массиве

public static int findMissing1(int [] arr){
    int sum = 0;
    for(int n : arr){
        sum += n;
    }
    return (100*(100+1)/2) - sum;
}

объяснение:
Это решение (как и многие другие решения, размещенные здесь) основано на Формуле Triangular number, что дает нам сумму всех натуральных чисел от 1 до n (в данном случае n на 100). Теперь, когда мы знаем сумму, которая должна быть от 1 до 100 — нам просто нужно вычесть фактическую сумму существующих чисел в данном массиве.

решение 2:

массив чисел от 1 до n (это означает, что максимальное число неизвестно)

public static int findMissing2(int [] arr){
    int sum = 0, max = 0;
    for(int n : arr){
        sum += n;
        if(n > max) max = n;
    }
    return (max*(max+1)/2) - sum;
}

объяснение:
В этом решении, поскольку максимальное число не задано-нам нужно его найти. После нахождения максимального числа-логика та же.

решение 3:

массив чисел от 1 до n (максимальное число неизвестно), есть два случайных пустых слота в массиве

public static int [] findMissing3(int [] arr){
    int sum = 0, max = 0, misSum;
    int [] misNums = {};//empty by default
    for(int n : arr){
        sum += n;
        if(n > max) max = n;
    }
    misSum = (max*(max+1)/2) - sum;//Sum of two missing numbers
    for(int n = Math.min(misSum, max-1); n > 1; n--){
        if(!contains(n, arr))misNums = new int[]{n, misSum-n};

    }
    return misNums;
}
private static boolean contains(int num, int [] arr){
    for(int n : arr){
        if(n == num)return true;
    }
    return false;
}

объяснение:
В этом решении максимальное число не задано (как и в предыдущем), но также может отсутствовать два числа, а не одно. Поэтому сначала мы находим сумму недостающих чисел-с той же логикой, что и раньше. Во-вторых, найти меньшее число между недостающей суммой и последней (возможно) недостающее число-для уменьшения ненужного поиска. В-третьих, начиная с Javaмассив s (не коллекция) не имеет методов как indexOf или contains, я добавил небольшой многоразовый метод для этой логики. В-четвертых, когда первое отсутствующее число найдено, второе-это вычесть из отсутствующей суммы.
Если отсутствует только одно число, то второе число в массиве будет равно нулю.

Примечание

если вы хотите примеры в другие языки или другой интересные вариации этого вопроса, вы можете проверить мои Github хранилище интервью вопросы и ответы.