Вопрос 1. Если у нас есть массив, в котором все элементы повторяются дважды, и только один элемент не повторяется.
{2, 4, 7, 1, 2, 4, 1}
It should return 7
Есть много способов решить эту проблему, но мы сделаем это с помощью манипуляций с битами.
В битовой манипуляции существует концепция, называемая X ИЛИ(^), она может включать бит, когда биты разные, и выключать биты, если они одинаковые.
0 ^ 0 -> 0 0 ^ 1 -> 1 1 ^ 0 -> 1 1 ^ 1 -> 0
Это означает, что если мы сравним число с самим собой, оно будет отменено и приведет к 0 (a^a -> 0). Мы можем использовать это свойство, чтобы отменить повторяющиеся числа.
Мы проведем итерацию по массиву и исключим все элементы массива, все повторяющиеся элементы в массиве отменят сами себя, и останется только число, которое не повторяется.
public int nonRepeating(int[] arr){
int res=0;
for(int val: arr){
res^=val;
}
return res;
}
Вопрос 2. Что, если у нас есть массив повторяющихся целых чисел, и теперь два элемента не повторяются? Шаг 1: Мы найдем XOR, как и в предыдущем примере. Теперь у нас будет значение, которое является XOR из двух чисел, если быть точным, не повторяющихся двух чисел. Шаг 2: Мы должны найти одно число из этих двух чисел, различая два числа. Шаг 3: Вычеркните одно число из результата, и мы также сможем получить второе число.
Input: {2, 4, 7, 9, 2, 4}
Step 1: res = 7^9
Step 2: Find 7 somehow
Step 3: 7^7^9 = 9
We have the answer now
Но главный вопрос в том, как мы планируем найти 7?
- Найдите первое вхождение 1 от самого правого (LSB) и сделайте число, где в этой позиции есть 1. {что означает, что один из битов числа в этой позиции равен 0, а другие – 1, так как XOR дает 1 только тогда, когда биты разные.}
- & это число со всеми элементами массива.
- Если результат & больше 0, это означает, что в этом значении также присутствует 1. Результатом этого будет одно из чисел, присутствующих в результате.
Хуже сказано, чем сделано , Давайте посмотрим на пример
Input: {2, 4, 7, 9, 2, 4}
Result: 7^9 -> 0111 ^ 1001 -> 1110 {first occurrence is at 1st position}
temp -> 0010 {1 at 1st position}
& temp with all values in array
{ this will results in >0 if the number has 1 in 1st position }
{ in this step we are dividing array in two parts, one part
contains the numbers which has 1 in in their 1st position and
second part where they don't have 1 in there 1st position }
After this if the result is >0, we will XOR all the numbers in this group with result(7^9) and that will give us 9.
How?
2 -> 0010 ^ 0010 -> 2>0 { XOR with res -> 7^9^2 }
4 -> 0100 ^ 0010 -> 0!>0 {skip}
7 -> 0111 ^ 0010 -> 2>0 { XOR with res -> 7^9^2^7 -> 9^2}
9 -> 1001 ^ 0010 -> 0!>0 {skip}
2 -> 0010 ^ 0010 -> 2>0 { XOR with res -> 9^2^2 -> 9}
4 -> 0100 ^ 0010 -> 0!>0 {skip}
Hence we get out result 9
Теперь, когда мы получаем 9, мы можем просто получить 7, зафиксировав результат с 9.
public void getNonRepeating(int[] arr){
int res=0;
for(int val:arr){
res^=val;
}
int temp=res&-res; //to get first set bit {2nd compliment}
int first=res;
for(int val:arr){
if((temp&val)>0)
first^=val;
}
int second=res^first;
System.out.println(first+" "+second);
}
Миссия выполнена!
Оригинал: “https://dev.to/prateekbud/find-non-repeating-element-from-repeating-array-179a”