求出现次数大于一半的数
在网上查了一下，这个题目大概有这几种做法：
一，用 map 计数，但是没有利用次数大于一半的特点，时间复杂度其实不是 O(N)，因为 map 也要计算，时间复杂度应该是 O(N^logN)。
二，遍历数组，元素两两比较，如果两个数相同，则删除一个，如果两个数不同，则都删除。这种方法的正确性我还没有证明。但是有一点是如果不存在次数大于一半的数，找到的结果肯定是错误的。这种方法是时间复杂度是 O(N)
三，还是遍历数组，这里用两个遍历 A 和 B 做记录工作。B 初始化 0，扫描整个数组，当 B == 0 时，A 等于当前数；如果当前数与 A 相同，则 ++B，如果与 A 不同，则 --A。遍历结束时，A 就是结果。时间复杂度是 O(N)。但是当数组中不存在次数大于一半的数时，这种方法找到的数还是不是正确的。
不过综合起来看，如果默认一定存在出现次数大于一半的数，那么第三种方法是最好的，思路清晰，实现简单。
下面是对第三种方法的实现：
1 #include <vector>
2 #include <iostream>
3 using namespace std;
4
5 int foo(const vector<int>& data)
6 {
7 int A, B = 0;
8 for (size_t i = 0; i != data.size(); ++i)
9 {
10 if (B == 0)
11 {
12 A = data[i];
13 }
14 if (A == data[i])
15 {
16 ++B;
17 }
18 else
19 {
20 --B;
21 }
22 }
23 return A;
24 }
25
26 int main()
27 {
28 vector<int> data;
29 for (int i = 0; i < 10; ++i)
30 {
31 data.push_back(5);
32 }
33 for (int i = 0; i < 10; ++i)
34 {
35 data.push_back(7);
36 }
37 data.push_back(7);
38 cout << foo(data) << endl;
39 return 0;
40 }
http://hi.baidu.com/mianshiti/blog/item/ac88ddeef9e29c4479f0556c.htmlhttp://blog.csdn.net/cynhafa/archive/2011/04/26/6364604.aspxhttp://blog.csdn.net/kannju/archive/2010/12/21/6090423.aspx
posted on 2011-05-21 11:06
unixfy 阅读(203)
评论(0) 编辑 收藏 引用