найти единственный непарный элемент в массиве

Question

Вопрос интервью Accenture:

Вам дан массив размером 2n+1, который имеет n пару целых чисел (может быть +ve, -ve или 0) и один непарный элемент.

Как бы вы нашли непарный элемент?

Пара означает дубликат . Таким образом, (3,3) является парой, а (3,-3) является , а не парой.

Answer 1

Взять 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.
}

Answer 2

Лучший ответ - оператор 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];
}

Answer 3

Пример строки Linq с решением XOR:

Демонстрация по 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);
}

Для удовольствия и выгоды

Edit:

Объяснение для этого фрагмента.

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 ;)

Answer 4

Альтернативное решение, чтобы найти все уникальные значения в O (n) и O (n) пространстве:

Инициализировать хэш-таблицу.
Для каждого значения в массиве проверьте, существует ли значение в хэш-таблице, если оно существует, удалите его, если нет, добавьте.
Возвращаемое значение - это все элементы внутри хэш-таблицы.

Может быть легко изменен для использования словаря, если повторяющиеся значения могут повторяться более одного раза.

Answer 5

Выполнить XOR среди всех элементов данного массива

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

Answer 6

Вот простое LINQ решение, которое можно легко расширить, чтобы обеспечить количество вхождений каждого уникального элемента:

     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);
     }

Выход:

Unpaired elements:
-1
0
5

Answer 7

Лучшее решение с использованием JavaScript, заняло у меня некоторое время.

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

С помощью метода Reduce код будет суммировать все числа кумулятивно, но так как Парс (a, b), использующий XOR, отменяет друг друга, только номер без номинала быть возвращенным.

Answer 8

Это тоже хорошее решение. В этом примере у нас есть один проход цикла.

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]);