Извлеките 2 места в массиве размером 10000, заполненных целыми числами от 1 до 10000. Как вы узнаете, каковы эти значения?

Возможный дубликат:Вопрос о простом интервью усложнился: с учетом номеров 1..100, найдите недостающие номера

Если у вас есть массив размером 10000, заполненный целыми числами от 1 до 10000, повторений нет, и вы устанавливаете два местоположения в этом массиве равным 0. Как вы выяснили, каковы эти два числа?

Например: Array = {8,6,3,5,4,2,7,1};//Массив заполнен с номерами от 1 до 8 просто для простоты.

Array [0] = 0; Массив [1] = 0;

Что было в позициях Array [0] и Array [1]?

Если вопрос оставил только одну нулевую позицию, проблема была бы легкой. Вы принимали бы сумму чисел от 1 до 8, что равно 36, и вычтите ее из суммы, которую вы получите, когда суммируете все числа в массиве после того, как позиция была равна нулю.

Это не проблема домашней работы. Но я думаю, что помню, как меня спрашивали в колледже.

4 ответа

Вы можете решить свою проблему с постоянной памятью и одним поиском массива:

  • Вы можете найти сумму нулевых чисел - путем вычисления суммы всего числа минус сумма оставшихся
  • Аналогичным образом вы можете найти сумму квадратов нулевых чисел (будьте осторожны, чтобы выбирать типы номеров, которые могут содержать достаточно большие значения).

Теперь у вас есть система из 2 уравнений с 2 ​​переменными (x + y == sum1 и x * x + y * y == sum2), которые могут быть легко решены.


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

Например: Array = {8,6,3,5,4,2,7,1};//Массив заполнен с номерами от 1 до 8 просто для простоты. Массив [0] = 0; Массив [1] = 0;

Исходная сумма = 36 Новая сумма = 28 Разница = 8 Пары, которые суммируются до 8: 7/1, 6/2, 5/3, 4/4 Проверьте 6/2, посмотрите, что 6 и 2 все еще там, исключают эту пару. Продолжайте, пока не найдете пару, в которой ни один номер не находится в массиве. Это ваш ответ. В этом случае ни 7, ни 1 все еще находятся в массиве, поэтому это два числа, которые отсутствовали.


Вы можете создать набор с номерами от 1 до 10000, пройти через массив и удалить из набора все числа, с которыми вы сталкиваетесь в массиве. В конце массива ваш набор должен иметь два числа, которые были удалены.


Вы не могли знать, какие нулевые цифры в определенном месте массива, но вы могли бы узнать 2 числа, найдя отсутствующие номера. в вашем нет. набор.

licensed under cc by-sa 3.0 with attribution.