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

问题在于在while循环过程中我忘记了给high--和low++，然后出现了死循环。
这个问题明显告诉我们它不需要排序，只需要找出其中的坏小子就可以啦。
比较简单的做法是data.unique(),然后比较前面三个元素。
当然，我写一篇文章记录下来了。http://honwhy.ixiezi.com/?p=265 有兴趣的可以看一下。

Answer 2

太小题大作了。读取前3个数字:
1. 如果3个数字不都一样，给出不一样的那个，结束。
2. 如果都一样=X，整个数组扫过去，找到一个不等于X的数字，结束。

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

如果能够根据前几个数字判断出来不变的数字是123，那可以对整个序列求和对123取模，余数应该就是那个不一致的数，但也仅限于那个不一致的数字只出现一次。

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

可以后面的数字和前面的数字相减得出不同么？

Answer 6

全部异或起来就搞定了啊。

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

Answer 7

一直xor就行了。。。