在一堆数字中找出和其他数字不同的数字,如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()是标准库中一个算法,具体的效率我不是很懂,而且对于这道题目来说,有一个不好的地方是,破坏了数组的结构,不能回答类似“唯一元素的序号”的问题; 这个小问题已经没有多少可以继续探讨的内容了,但我觉得应该加上一个要求——不能破坏数据结构。
问题在于在while循环过程中我忘记了给high--和low++,然后出现了死循环。
这个问题明显告诉我们它不需要排序,只需要找出其中的坏小子就可以啦。
比较简单的做法是data.unique(),然后比较前面三个元素。
当然,我写一篇文章记录下来了。http://honwhy.ixiezi.com/?p=265 有兴趣的可以看一下。