搜尋

首頁  >  問答  >  主體

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

在一堆数字中找出和其他数字不同的数字,如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()是标准库中一个算法,具体的效率我不是很懂,而且对于这道题目来说,有一个不好的地方是,破坏了数组的结构,不能回答类似“唯一元素的序号”的问题; 这个小问题已经没有多少可以继续探讨的内容了,但我觉得应该加上一个要求——不能破坏数据结构
阿神阿神2808 天前1023

全部回覆(7)我來回復

  • 天蓬老师

    天蓬老师2017-04-17 11:04:06

    問題在於在while循環過程中我忘記了給high--low ,然後出現了死循環。
    這個問題明顯告訴我們它不需要排序,隻需要找出其中的壞小子就可以啦。
    比較簡單的做法是data.unique(),然後比較前麵三個元素。
    當然,我寫一篇文章記錄下來了。http://honwhy.ixiezi.com/?p=265 有興趣的可以看一下。

    回覆
    0
  • 怪我咯

    怪我咯2017-04-17 11:04:06

    太小題大作了。讀取前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;
    }

    回覆
    0
  • 高洛峰

    高洛峰2017-04-17 11:04:06

    如果能夠根據前幾個數字判斷出來不變的數字是123,那可以對整個序列求和對123取模,餘數應該就是那個不一致的數,但也僅限於那個不一致的數字隻出現一次。

    回覆
    0
  • ringa_lee

    ringa_lee2017-04-17 11:04:06

    雷雷

    回覆
    0
  • PHPz

    PHPz2017-04-17 11:04:06

    123,123,123,14,123,123

    可以後麵的數字和前麵的數字相減得出不同麼?

    回覆
    0
  • 高洛峰

    高洛峰2017-04-17 11:04:06

    全部異或起來就搞定了啊。

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

    回覆
    0
  • 高洛峰

    高洛峰2017-04-17 11:04:06

    一直xor就行了。。。

    回覆
    0
  • 取消回覆