Самый быстрый способ найти недостающее число в массиве чисел
У меня есть массив чисел от 1 до 100 (оба включительно). Размер массива равняется 100. Числа случайным образом добавляются к массиву, но в массиве существует один случайный пустой слот. Что самый быстрый путь состоит в том, чтобы найти, что слот, а также число, которое должно быть помещено в слот? Решение для Java предпочтительно.
5 ответов
Вы можете сделать это в O (n). Итайте через массив и вычислить сумму всех чисел. Теперь сумма натуральных чисел от 1 до N, может быть выражена как NX (N + 1) / 2 . В вашем случае n = 100.
Вычтите сумму массива из NX (N + 1) / 2 , где n = 100.
Это отсутствует номер. Пустой слот можно обнаружить во время итерации, в которой вычисляется сумма.
// will be the sum of the numbers in the array.
int sum = 0;
int idx = -1;
for (int i = 0; i < arr.length; i++)
{
if (arr[i] == 0)
{
idx = i;
}
else
{
sum += arr[i];
}
}
// the total sum of numbers between 1 and arr.length.
int total = (arr.length + 1) * arr.length / 2;
System.out.println("missing number is: " + (total - sum) + " at index " + idx);
Другой домашний вопрос. Последовательный поиск - лучшее, что вы можете сделать. Что касается решения Java, считайте, что упражнение для читателя. : P
Это C #, но это должно быть довольно близко к тому, что вам нужно:
int sumNumbers = 0;
int emptySlotIndex = -1;
for (int i = 0; i < arr.length; i++)
{
if (arr[i] == 0)
emptySlotIndex = i;
sumNumbers += arr[i];
}
int missingNumber = 5050 - sumNumbers;
5050 - (сумма всех значений в массиве) = отсутствующий номер
int sum = 0;
int idx = -1;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 0) idx = i; else sum += arr[i];
}
System.out.println("missing number is: " + (5050 - sum) + " at index " + idx);
Быстрый сортировка - лучший выбор с максимальной эффективностью ....