c++ - 如何在一堆数字中找出与其他数字不同的一个？

Question

在一堆数字中找出和其他数字不同的数字，如123,123,14,123,123,123这堆数字中找出14来，写下算法思路和时间复杂度，要求写核心代码和不能使用辅助空间。

#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
int main() { 

    vector<int> data;
	cout << "Enter same numbers "
			<< " and a different one( negative to be end) :" << endl;
	int value;
    while( cin >> value && value > 0 ) {
        data.push_back(value);
    }
    int unique_value;
    int size = data.size();
    if(data[0] != data[1] ) {
        if( data[0] != data[2]) {
            unique_value = data[0];
        }
        else  {
            unique_value = data[1];
        }
       cout << "found the unique number: " << unique_value << endl;
       exit(0);
    }
    int low = 2;
    int high = size-1;
    while( high > low )  {
         if( data[high] != data[low] ) {
            //其中必有一个是不同的，只要和data[0]就能得到结果
            if( data[high] != data[0] ) {
                unique_value = data[high];
            } 
            else {
                unique_value = data[low];
            }
            break;
         }
    }
    if( high == low ) 
   //low和high相等，data[high]没有和任何其他元素比较过
    unique_value = data[high];
    cout << "found the unique number: " << unique_value << endl;
    return 0;
}

这段代码有什么问题吗？
BUG已经找出来了，可以看我的答案。

分割线

但是或许表达的原因，题意不甚清楚，所以这里补充说明：

1.不一致的数字只出现一次，即所有数字的情况为：N个value_1和一个value_2，value_1不等于value_2；
2.为了方便输入数据演示，我们假设数字不能为负数；

大家都说得很好: unique()是标准库中一个算法，具体的效率我不是很懂，而且对于这道题目来说，有一个不好的地方是，破坏了数组的结构，不能回答类似“唯一元素的序号”的问题； 这个小问题已经没有多少可以继续探讨的内容了，但我觉得应该加上一个要求——不能破坏数据结构。

Answer 1

The problem is that during the while loop I forgot to give high-- and low , and then an infinite loop appeared.
This question obviously tells us that it does not need to be sorted, we only need to find the bad boy among them.
A simpler approach is data.unique(), and then compare the first three elements.
Of course, I wrote an article to record it. http://honwhy.ixiezi.com/?p=265 If you are interested, you can take a look.

Answer 2

What a fuss. Read the first 3 numbers:
1. If the three numbers are not the same, give the different one and end.
2. If they are all the same =X, scan the entire array, find a number that is not equal to X, and end it.

int foo(int x[], int n)
{
    int a = x[0], b = x[1], c = x[2];
    if (a == b && b == c)
        for (int i = 3; i < n; i++)
            if (x[i] != a)
                return x[i];
    if (a == b) return c;
    if (a == c) return b;
    return a;
}

Answer 3

If you can determine that the constant number is 123 based on the first few numbers, you can sum the entire sequence modulo 123. The remainder should be the inconsistent number, but it is limited to the inconsistent number appearing only once. .

Answer 4

int get_uniq(int * a)
{
    int i = 1;
    if (a[0]!=a[1])
        return a[0]^a[1]^a[2];
    else
        while (a[0]==a[++i]);
    return a[i];
}

Answer 5

123,123,123,14,123,123

Can the following number be subtracted from the previous number to get the difference?

Answer 6

Just XOR them all and you’re done.

int x=0;
for (int i=0;i<n; i) x=x^a[i];

Answer 7

Just keep xor. . .