배열에서 짝을 이루지 않은 유일한 요소 찾기

배열에서 짝을 이루지 않은 유일한 요소 찾기

---

Accenture 인터뷰 질문 :

한 쌍의 정수 ( 또는 일 수 있음 )와 하나의 쌍을 이루지 않는 요소 2n+1가있는 크기 배열이 제공되었습니다 .n+ve-ve0

페어링되지 않은 요소를 어떻게 찾을 수 있습니까?

쌍은 중복을 의미 합니다. 그래서 (3,3)한 쌍이며 (3,-3)입니다 하지 쌍.

---

XOR모든 요소를 취하십시오 .

쌍은 다음과 같이 취소됩니다.

a XOR a = 0

결과는 다음과 같이 짝을 이루지 않는 유일한 요소가됩니다.

0 XOR a = a

배열을 파괴해도 괜찮다면 XOR인접 요소 를 사용할 수 있습니다 . 완료되면 배열의 마지막 요소에 짝이없는 요소가 있습니다.

N = Num of elements in array.
for( i=1 to N )
   arr[i] ^= arr[i-1];    
print arr[N-1]

배열을 파괴해도 괜찮지 않다면 변수를 사용하여 결과를 유지할 수 있습니다.

N = Num of elements in array.
Unpaired = arr[0];
for( i=1 to N )
   Unpaired = Unpaired ^ arr[i];    
print Unpaired

동일한 작업을 수행하는 C 함수 :

int findUnpaired(int *arr,int len) {
 int i;                  // loop counter.
 int unpaired;           // to hold the unpaired element.

 unpaired = arr[0];      // initialize it with the 1st array ele.

 for(i=1;i<len;i++) {    // loop for all remaining elements.
    unpaired ^= arr[i];  // XOR each element with the running XOR.
 }
 return unpaired;        // return result.
}

---

O (n) 및 O (n) 공간에서 모든 고유 값 을 찾는 대체 솔루션 :

해시 테이블을 초기화합니다.
배열의 각 값에 대해 값이 Hash 테이블에 있는지 확인하고, 존재하는 경우 제거하고, 존재하지 않는 경우 추가합니다.
반환 값은 Hash 테이블 내의 모든 항목입니다.

반복 값이 두 번 이상 반복 될 수있는 경우 사전을 사용하도록 쉽게 수정할 수 있습니다.

---

XOR 솔루션이있는 단일 라인 Linq 예제 :

DotNetFiddle 데모

public static void Main()
{
    int[] tab = { 1, 2, 3, 2, 1 };
    Console.WriteLine(GetSingle(tab));
}

private static int GetSingle(IEnumerable<int> tab)
{
    return tab.Aggregate(0, (current, i) => current ^ i);
}

재미와 이익을 위해

편집하다:

이 스 니펫에 대한 설명.

var a = 2;
var b = 2;
Console.WriteLine(a ^ b); // will print 0
// because x ^ x == 0

var c = 3;
Console.WriteLine(a ^ b ^ c); // will print 3
// because 0 ^ x == x

Console.WriteLine(0 ^ a); // guess the output
// get it? :)
// Now, lets aggregate this enumerable ;)

---

가장 좋은 대답은 XOR 연산자입니다. 재미를 위해 다른 방법은 배열을 정렬 할 수있는 경우 정렬하고 인접한 정수를 비교하는 것입니다. 이것은 모든 정수가 정확히 두 번 나타나고 하나의 정수가 한 번 나타나는 것으로 가정합니다.

// Random array of integers
int[] arr = {1, 2, 3, 4, 5, 6, 7, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9};

// Sort the array.
Arrays.sort(arr);

// Array now looks like: 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 9 9 
// Cycle through array comparing adjacent values.
for(int i = 0; i < arr.length; i++){

    // This would mean the single number was the last element in the array.
    if(i == arr.length-1)
        singleNum = arr[i];

    // If the adjacent elements are the same, skip foward. 
    if(i < arr.length-1 && arr[i] == arr[i+1])
        i ++;
    else
        // Otherwise, you found the single number.
        singleNum = arr[i];
}

---

Here'a a simple LINQ solution that can easily be extended to provide the number of occurrences of each unique element:

     int[] numbers = { -1, 0, 1, 2, 3, 4, 5, 4, 3, 2, 1 };

     var numberGroups =
         from n in numbers
         group n by n into g
         select new { Number = g.Key, IsPaired = g.Count() == 2 };

     Console.WriteLine("Unpaired elements:");
     foreach (var group in numberGroups)
     {
        if (!group.IsPaired)
           Console.WriteLine(group.Number);
     }

Output:

Unpaired elements:
-1
0
5

---

Perform XOR among all elements of the given array

def unpaired(arr):
    result = 0
    for i in arr:
        result = result^i
    return result

---

It's a good solution too. In this example, we have one cycle passage.

function getUpaired(arr) {
    var obj = {};
    for (var i = 0; i < arr.length; i++) {
        if (typeof obj[arr[i]] !== 'undefined') {
            delete obj[arr[i]];
            continue;
        }
    obj[arr[i]] = i;
    }
    return Number(Object.keys(obj)[0]);
}
getUpaired([0,0,2,1,3,2,1]);

---

Best solution using JavaScript, took me some time.

    var singleNumber = function(nums) {
       return nums.reduce((a,b) => a^b);
    };

Using reduce, code will add all of the numbers cumulatively, but since the pars (a, b) using XOR cancel each other out, only the number without the par will be returned.

---

If you are using Swift you can find unpaired element with following code

func findUnpaired(_ arr: [Int]) -> Int {
    return arr.reduce(0, +)
}

ReferenceURL : https://stackoverflow.com/questions/2644179/find-the-only-unpaired-element-in-the-array