Как найти в массиве целые числа

There is a standard algorithm to solve such problems using XOR operator:

Time Complexity = O(n)

Space Complexity = O(1)

Suppose your input array contains only one element that occurs odd no of times and rest occur even number of times,we take advantage of the following fact:

Any expression having even number of 0’s and 1’s in any order will always be = 0 when xor is applied.

That is

0^1^....... = 0 as long as number of 0 is even and number of 1 is even 

and 0 and 1 can occur in any order.

Because all numbers that occur even number of times will have their corresponding bits form even number of 1’s and 0’s and only the number which occurs only once will have its bit left out when we take xor of all elements of array because

0(from no's occuring even times)^1(from no occuring once) = 1 

0(from no's occuring even times)^0(from no occuring once) = 0

as you can see the bit of only the number occuring once is preserved.

This means when given such an array and you take xor of all the elements,the result is the number which occurs only once.

So the algorithm for array of length n is:

 result = array[0]^array[1]^.....array[n-1] 

Different Scenario

As the OP mentioned that input can also be an array which has two numbers occuring only once and rest occur even number of times.

This is solved using the same logic as above but with little difference.

Idea of algorithm:

If you take xor of all the elements then definitely all the bits of elements occuring even number of times will result in 0,which means:

The result will have its bit 1 only at that bit position where the bits of the two numbers occuring only once differ.

We will use the above idea.

Now we focus on the resultant xor bit which is 1(any bit which is 1) and make rest 0.The result is a number which will allow us to differentiate between the two numbers(the required ones).

Because the bit is 1,it means they differ at this position,it means one will have 0 at this position and one will have 1.This means one number when taken AND results in 0 and one does not.

Since it is very easy to set the right most bit,we set it of the result xor as

 A = result & ~(result-1)

Now traverse through the array once and if array[i]&A is 0 store the number in variable number_1 as

 number_1 = number_1^array[i]

otherwise

 number_2 = number_2^array[i]

Because the remaining numbers occur even number of times,their bit will automatically disappear.

So the algorithm is

1.Take xor of all elements,call it xor.

2.Set the rightmost bit of xor and store it in B.

3.Do the following:

number_1=0,number_2=0;
for(i = 0 to n-1)
{
 if(array[i] & B)
  number_1 = number_1^array[i];
 else
  number_2 = number_2^array[i];
}

The number_1 and number_2 are the required numbers.

Учитывая массив 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 это размер ввода.