求出現次數大于一半的數
在網上查了一下，這個題目大概有這幾種做法：
一，用 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 閱讀(209)
評論(0) 編輯 收藏 引用