У меня есть массив чисел от 1 до 100 (оба включительно). Размер массива равен 100. Числа случайным образом добавляются в массив, но в массиве есть один случайный пустой слот. Каков самый быстрый способ найти этот слот, а также номер, который нужно поместить в слот? Предпочтительным является решение Java.
Самый быстрый способ найти недостающее число в массиве чисел
Ответ 1
Вы можете сделать это в 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);
Ответ 2
long n = 100;
int a[] = new int[n];
//XOR of all numbers from 1 to n
// n%4 == 0 ---> n
// n%4 == 1 ---> 1
// n%4 == 2 ---> n + 1
// n%4 == 3 ---> 0
long xor = (n % 4 == 0) ? n : (n % 4 == 1) ? 1 : (n % 4 == 2) ? n + 1 : 0;
for (long i = 1; i <= n; i++)
{
xor = xor ^ a[i];
}
//Missing number
System.out.println(xor);
Ответ 3
Мы можем использовать операцию XOR, которая более безопасна, чем суммирование, потому что в языках программирования, если данный вход большой, он может переполняться и может давать неправильный ответ.
Прежде чем перейти к решению, знайте, что A xor A = 0. Поэтому, если мы имеем XOR два одинаковых числа, значение равно 0.
Теперь XORing [1..n] с элементами, присутствующими в массиве, отменяет одинаковые числа. Поэтому в конце мы получим недостающее число.
// Assuming that the array contains 99 distinct integers between 1..99
// and empty slot value is zero
int XOR = 0;
for(int i=0; i<100; i++) {
if (ARRAY[i] != 0)
XOR ^= ARRAY[i];
XOR ^= (i + 1);
}
return XOR;
Ответ 4
Это был вопрос интервью с Amazon, и на нем был первоначально дан ответ: У нас есть номера от 1 до 52, которые помещаются в массив чисел 51, что лучший способ чтобы узнать, какое число отсутствует?
На это был дан ответ, как показано ниже:
1) Calculate the sum of all numbers stored in the array of size 51.
2) Subtract the sum from (52 * 53)/2 ---- Formula : n * (n + 1) / 2.
Здесь также были представлены блоги: Работа с программным обеспечением - вопрос о себе
Ответ 5
Вот простая программа для поиска недостающих чисел в целочисленном массиве
ArrayList<Integer> arr = new ArrayList<Integer>();
int a[] = { 1,3,4,5,6,7,10 };
int j = a[0];
for (int i=0;i<a.length;i++)
{
if (j==a[i])
{
j++;
continue;
}
else
{
arr.add(j);
i--;
j++;
}
}
System.out.println("missing numbers are ");
for(int r : arr)
{
System.out.println(" " + r);
}
Ответ 6
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);
Ответ 7
Это С#, но он должен быть близок к тому, что вам нужно:
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;
Ответ 8
Ну, используйте фильтр цветения.
int findmissing(int arr[], int n)
{
long bloom=0;
int i;
for(i=0; i<;n; i++)bloom+=1>>arr[i];
for(i=1; i<=n, (bloom<<i & 1); i++);
return i;
}
Ответ 9
В аналогичном сценарии , где массив уже отсортирован, он не включает дубликаты и не хватает только одного номера, можно найти это недостающее число в журнале (n) время, используя двоичный поиск.
public static int getMissingInt(int[] intArray, int left, int right) {
if (right == left + 1) return intArray[right] - 1;
int pivot = left + (right - left) / 2;
if (intArray[pivot] == intArray[left] + (intArray[right] - intArray[left]) / 2 - (right - left) % 2)
return getMissingInt(intArray, pivot, right);
else
return getMissingInt(intArray, left, pivot);
}
public static void main(String args[]) {
int[] array = new int[]{3, 4, 5, 6, 7, 8, 10};
int missingInt = getMissingInt(array, 0, array.length-1);
System.out.println(missingInt); //it prints 9
}
Ответ 10
Решение, которое не включает повторяющиеся дополнения или, может быть, формулу n (n + 1)/2, не попадает вам на собеседование, например.
Вы должны использовать массив из 4 целых (32 бита) или 2 int (64 бит). Инициализируйте последний int с (-1 и ~ (1 < 31)) → 3. (биты, которые превышают 100, установлены в 1). Или вы можете установить биты выше 100, используя цикл for.
- Пройдите по массиву чисел и установите 1 для позиции бита, соответствующей номеру (например, 71 будет установлен на третьем int на 7-м бите слева направо)
- Пройдите через массив из 4-х int (32-разрядная версия) или 2 ints (64-разрядная версия)
public int MissingNumber(int a[])
{
int bits = sizeof(int) * 8;
int i = 0;
int no = 0;
while(a[i] == -1)//this means a[i] bits are all set to 1, the numbers is not inside this 32 numbers section
{
no += bits;
i++;
}
return no + bits - Math.Log(~a[i], 2);//apply NOT (~) operator to a[i] to invert all bits, and get a number with only one bit set (2 at the power of something)
}
Пример: (32-разрядная версия) позволяет сказать, что недостающее число равно 58. Это означает, что 26-й бит (слева направо) второго целого числа равен 0.
Первый int равен -1 (все биты установлены), поэтому мы переходим ко второму и добавляем "no" число 32. Второй int отличается от -1 (бит не установлен), поэтому, применяя оператор NOT (~) к числу, которому мы получаем 64. Возможные числа равны 2 при мощности x, и мы можем вычислить x, используя log на основании 2; в этом случае мы получаем log2 (64) = 6 = > 32 + 32 - 6 = 58.
Надеюсь, что это поможет.
Ответ 11
Это не проблема поиска. Работодатель задается вопросом, есть ли у вас хватка контрольной суммы. Вам может понадобиться двоичный или цикл или что-то еще, если вы ищете несколько уникальных целых чисел, но вопрос предусматривает "один случайный пустой слот". В этом случае мы можем использовать сумму потока. Условие: "Числа, случайно добавленные в массив", бессмысленны без дополнительных деталей. Вопрос не предполагает, что массив должен начинаться с целого числа 1 и, таким образом, терпеть его с целым числом начала смещения.
int[] test = {2,3,4,5,6,7,8,9,10, 12,13,14 };
/*get the missing integer*/
int max = test[test.length - 1];
int min = test[0];
int sum = Arrays.stream(test).sum();
int actual = (((max*(max+1))/2)-min+1);
//Find:
//the missing value
System.out.println(actual - sum);
//the slot
System.out.println(actual - sum - min);
Время успеха: 0,18 память: 320576 сигнал: 0
Ответ 12
Я нашел это красивое решение здесь:
http://javaconceptoftheday.com/java-puzzle-interview-program-find-missing-number-in-an-array/
public class MissingNumberInArray
{
//Method to calculate sum of 'n' numbers
static int sumOfNnumbers(int n)
{
int sum = (n * (n+1))/ 2;
return sum;
}
//Method to calculate sum of all elements of array
static int sumOfElements(int[] array)
{
int sum = 0;
for (int i = 0; i < array.length; i++)
{
sum = sum + array[i];
}
return sum;
}
public static void main(String[] args)
{
int n = 8;
int[] a = {1, 4, 5, 3, 7, 8, 6};
//Step 1
int sumOfNnumbers = sumOfNnumbers(n);
//Step 2
int sumOfElements = sumOfElements(a);
//Step 3
int missingNumber = sumOfNnumbers - sumOfElements;
System.out.println("Missing Number is = "+missingNumber);
}
}
Ответ 13
======== Простейшее решение для отсортированного массива ===========
public int getMissingNumber(int[] sortedArray)
{
int missingNumber = 0;
int missingNumberIndex=0;
for (int i = 0; i < sortedArray.length; i++)
{
if (sortedArray[i] == 0)
{
missingNumber = (sortedArray[i + 1]) - 1;
missingNumberIndex=i;
System.out.println("missingNumberIndex: "+missingNumberIndex);
break;
}
}
return missingNumber;
}
Ответ 14
Поиск недостающего числа из серии чисел. IMP указывает, чтобы помнить.
- массив должен быть отсортирован.
- Функция не работает с несколькими пропущенными сообщениями.
-
последовательность должна быть точкой доступа.
public int execute2(int[] array) { int diff = Math.min(array[1]-array[0], array[2]-array[1]); int min = 0, max = arr.length-1; boolean missingNum = true; while(min<max) { int mid = (min + max) >>> 1; int leftDiff = array[mid] - array[min]; if(leftDiff > diff * (mid - min)) { if(mid-min == 1) return (array[mid] + array[min])/2; max = mid; missingNum = false; continue; } int rightDiff = array[max] - array[mid]; if(rightDiff > diff * (max - mid)) { if(max-mid == 1) return (array[max] + array[mid])/2; min = mid; missingNum = false; continue; } if(missingNum) break; } return -1; }
Ответ 15
Я думаю, что самым простым и, возможно, самым эффективным решением было бы перебрать все записи и использовать битрейт, чтобы запомнить, какие числа установлены, а затем проверить на 0 бит. Запись с 0 бит - это недостающее число.
Ответ 16
Эта программа находит недостающие номера
<?php
$arr_num=array("1","2","3","5","6");
$n=count($arr_num);
for($i=1;$i<=$n;$i++)
{
if(!in_array($i,$arr_num))
{
array_push($arr_num,$i);print_r($arr_num);exit;
}
}
?>
Ответ 17
Одна вещь, которую вы можете сделать, это сортировать числа, используя, например, быстрый сортировку. Затем используйте цикл for для итерации через отсортированный массив от 1 до 100. На каждой итерации вы сравниваете число в массиве с вашим приращением для цикла, если вы обнаружите, что приращение индекса не совпадает с значением массива, вы нашли недостающее число, а также отсутствующий индекс.
Ответ 18
Ниже приведено решение для нахождения всех недостающих чисел из заданного массива:
public class FindMissingNumbers {
/**
* The function prints all the missing numbers from "n" consecutive numbers.
* The number of missing numbers is not given and all the numbers in the
* given array are assumed to be unique.
*
* A similar approach can be used to find all no-unique/ unique numbers from
* the given array
*
* @param n
* total count of numbers in the sequence
* @param numbers
* is an unsorted array of all the numbers from 1 - n with some
* numbers missing.
*
*/
public static void findMissingNumbers(int n, int[] numbers) {
if (n < 1) {
return;
}
byte[] bytes = new byte[n / 8];
int countOfMissingNumbers = n - numbers.length;
if (countOfMissingNumbers == 0) {
return;
}
for (int currentNumber : numbers) {
int byteIndex = (currentNumber - 1) / 8;
int bit = (currentNumber - byteIndex * 8) - 1;
// Update the "bit" in bytes[byteIndex]
int mask = 1 << bit;
bytes[byteIndex] |= mask;
}
for (int index = 0; index < bytes.length - 2; index++) {
if (bytes[index] != -128) {
for (int i = 0; i < 8; i++) {
if ((bytes[index] >> i & 1) == 0) {
System.out.println("Missing number: " + ((index * 8) + i + 1));
}
}
}
}
// Last byte
int loopTill = n % 8 == 0 ? 8 : n % 8;
for (int index = 0; index < loopTill; index++) {
if ((bytes[bytes.length - 1] >> index & 1) == 0) {
System.out.println("Missing number: " + (((bytes.length - 1) * 8) + index + 1));
}
}
}
public static void main(String[] args) {
List<Integer> arrayList = new ArrayList<Integer>();
int n = 128;
int m = 5;
for (int i = 1; i <= n; i++) {
arrayList.add(i);
}
Collections.shuffle(arrayList);
for (int i = 1; i <= 5; i++) {
System.out.println("Removing:" + arrayList.remove(i));
}
int[] array = new int[n - m];
for (int i = 0; i < (n - m); i++) {
array[i] = arrayList.get(i);
}
System.out.println("Array is: " + Arrays.toString(array));
findMissingNumbers(n, array);
}
}
Ответ 19
Предположим, что у вас n равно 8, а наши номера варьируются от 0 до 8 для этого примера мы можем представить двоичное представление всех 9 чисел следующим образом 0000 0001 0010 0011 0100 0101 0110 0111 1000
в приведенной выше последовательности нет недостающих чисел, и в каждом столбце число совпадений и совпадений совпадает, однако, как только вы удаляете 1 значение, скажем 3, мы получаем баланс в количестве 0 и 1 по столбцам, Если число 0 в столбце равно <= число 1, наше недостающее число будет иметь 0 в этой битовой позиции, в противном случае, если число 0 > число 1 в этой битовой позиции, то это битовая позиция будет 1. Мы тестируем бит слева направо, и на каждой итерации мы выбрасываем половину массива для тестирования следующего бита, либо нечетные значения массива, либо четные значения массива отбрасываются на каждой итерации в зависимости от того, какой бит мы недостаток.
Нижеприведенное решение находится в С++
int getMissingNumber(vector<int>* input, int bitPos, const int startRange)
{
vector<int> zeros;
vector<int> ones;
int missingNumber=0;
//base case, assume empty array indicating start value of range is missing
if(input->size() == 0)
return startRange;
//if the bit position being tested is 0 add to the zero vector
//otherwise to the ones vector
for(unsigned int i = 0; i<input->size(); i++)
{
int value = input->at(i);
if(getBit(value, bitPos) == 0)
zeros.push_back(value);
else
ones.push_back(value);
}
//throw away either the odd or even numbers and test
//the next bit position, build the missing number
//from right to left
if(zeros.size() <= ones.size())
{
//missing number is even
missingNumber = getMissingNumber(&zeros, bitPos+1, startRange);
missingNumber = (missingNumber << 1) | 0;
}
else
{
//missing number is odd
missingNumber = getMissingNumber(&ones, bitPos+1, startRange);
missingNumber = (missingNumber << 1) | 1;
}
return missingNumber;
}
На каждой итерации мы сокращаем наше входное пространство на 2, т.е. N, N/2, N/4... = O (log N), с пространством O (N)
//Test cases
[1] when missing number is range start
[2] when missing number is range end
[3] when missing number is odd
[4] when missing number is even
Ответ 20
Решение С PHP $n = 100;
$n*($n+1)/2 - array_sum($array) = $missing_number
и array_search($missing_number) даст индекс недостающего числа
Ответ 21
function solution($A) {
// code in PHP5.5
$n=count($A);
for($i=1;$i<=$n;$i++) {
if(!in_array($i,$A)) {
return (int)$i;
}
}
}
Ответ 22
Здесь сложность времени выполнения программы - это O (logn) и сложность пространства O (logn)
public class helper1 {
public static void main(String[] args) {
int a[] = {1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 12};
int k = missing(a, 0, a.length);
System.out.println(k);
}
public static int missing(int[] a, int f, int l) {
int mid = (l + f) / 2;
//if first index reached last then no element found
if (a.length - 1 == f) {
System.out.println("missing not find ");
return 0;
}
//if mid with first found
if (mid == f) {
System.out.println(a[mid] + 1);
return a[mid] + 1;
}
if ((mid + 1) == a[mid])
return missing(a, mid, l);
else
return missing(a, f, mid);
}
}
Ответ 23
public class MissingNumber {
public static void main(String[] args) {
int array[] = {1,2,3,4,6};
int x1 = getMissingNumber(array,6);
System.out.println("The Missing number is: "+x1);
}
private static int getMissingNumber(int[] array, int i) {
int acctualnumber =0;
int expectednumber = (i*(i+1)/2);
for (int j : array) {
acctualnumber = acctualnumber+j;
}
System.out.println(acctualnumber);
System.out.println(expectednumber);
return expectednumber-acctualnumber;
}
}
Ответ 24
Недавно у меня был аналогичный (не совсем тот же) вопрос в собеседовании, а также я услышал от друга, которого задали точно такой же вопрос в интервью. Итак, вот ответ на вопрос 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 Array (а не коллекция) не имеет методов как indexOf или contains, я добавил небольшой метод повторного использования для этой логики. В-четвертых, когда первое пропущенное число найдено, второе - это вычитание из недостающей суммы.
Если отсутствует только одно число, тогда второе число в массиве будет равно нулю.
Примечание
Если вам нужны примеры из других языков или других интересных вариантов этого вопроса, вы можете проверить мой репозиторий Github для Интервью с вопросами и ответами.
Ответ 25
Использовать формулу суммы,
class Main {
// Function to ind missing number
static int getMissingNo (int a[], int n) {
int i, total;
total = (n+1)*(n+2)/2;
for ( i = 0; i< n; i++)
total -= a[i];
return total;
}
/* program to test above function */
public static void main(String args[]) {
int a[] = {1,2,4,5,6};
int miss = getMissingNo(a,5);
System.out.println(miss);
}
}
Ссылка http://www.geeksforgeeks.org/find-the-missing-number/
Ответ 26
//Array is shorted and if writing in C/C++ think of XOR implementations in java as follows.
int num=-1;
for (int i=1; i<=100; i++){
num =2*i;
if(arr[num]==0){
System.out.println("index: "+i+" Array position: "+ num);
break;
}
else if(arr[num-1]==0){
System.out.println("index: "+i+ " Array position: "+ (num-1));
break;
}
}// use Rabbit and tortoise race, move the dangling index faster,
//learnt from Alogithimica, Ameerpet, hyderbad**
Ответ 27
Если массив случайным образом заполнен, то в лучшем случае вы можете выполнить линейный поиск по сложности O (n). Тем не менее, мы могли бы улучшить сложность O (log n) путем разделения и захвата, аналогичного быстрой сортировке, как указано giri, учитывая, что числа были в порядке возрастания/убывания.
Ответ 28
Теперь я теперь слишком острый с нотами Big O, но не мог бы вы также сделать что-то вроде (на Java)
for (int i = 0; i < numbers.length; i++) {
if(numbers[i] != i+1){
System.out.println(i+1);
}
}
где числа - это массив с вашими номерами от 1 до 100. Из моего чтения вопроса он не сказал, когда нужно выписать недостающее число.
Альтернативно, если вы МОЖЕТЕ выбросить значение я + 1 в другой массив и распечатать его после итерации.
Конечно, это может не соответствовать правилам времени и пространства. Как я сказал. Я должен сильно расчесывать Big O.
Ответ 29
Другой вопрос о домашнем задании. Последовательный поиск - это лучшее, что вы можете сделать. Что касается решения Java, рассмотрите это упражнение для читателя.: P
Ответ 30
Быстрая сортировка - лучший выбор с максимальной эффективностью....