找到整数数组中的发生两次 [英] Find integer not occurring twice in an array

问题描述

我试图来解决这个问题： 在一个整数数组中发生的所有确切的数字的两倍，除了它出现一次单号。

I am trying to solve this problem: In an integer array all numbers occur exactly twice, except for a single number which occurs exactly once.

有一个简单的解决方案是将数组排序，然后测试不重复。但我要寻找更好的解决方案，有时间为O（n）的复杂性。

A simple solution is to sort the array and then test for non repetition. But I am looking for better solution that has time complexity of O(n).

推荐答案

您可以使用整个阵列的异或操作。每一对数字将相互抵消，使你的追求价值。

You can use "xor" operation on the entire array. Each pair of numbers will cancel each other, leaving you with the sought value.

int get_orphan(int const * a, int len)
{
    int value = 0;
    for (int i = 0; i < len; ++i)
        value ^= a[i];

    // `value` now contains the number that occurred odd number of times.
    // Retrieve its index in the array.
    for (int i = 0; i < len; ++i)
    {
        if (a[i] == value)
            return i;
    }

    return -1;
}

这篇关于找到整数数组中的发生两次的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！