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

Ответ 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.
}

Ответ 2

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

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

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

Ответ 3

Пример Linq 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 ;)

Ответ 4

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

Ответ 5

Вот простой решение 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

Ответ 6

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

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

Ответ 7

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

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

Ответ 8

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

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

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

Ответ 9

Если вы используете Swift, вы можете найти непарный элемент со следующим кодом

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