求出現(xiàn)次數(shù)大于一半的數(shù)
在網(wǎng)上查了一下，這個題目大概有這幾種做法：
一，用 map 計數(shù)，但是沒有利用次數(shù)大于一半的特點，時間復(fù)雜度其實不是 O(N)，因為 map 也要計算，時間復(fù)雜度應(yīng)該是 O(N^logN)。
二，遍歷數(shù)組，元素兩兩比較，如果兩個數(shù)相同，則刪除一個，如果兩個數(shù)不同，則都刪除。這種方法的正確性我還沒有證明。但是有一點是如果不存在次數(shù)大于一半的數(shù)，找到的結(jié)果肯定是錯誤的。這種方法是時間復(fù)雜度是 O(N)
三，還是遍歷數(shù)組，這里用兩個遍歷 A 和 B 做記錄工作。B 初始化 0，掃描整個數(shù)組，當(dāng) B == 0 時，A 等于當(dāng)前數(shù)；如果當(dāng)前數(shù)與 A 相同，則 ++B，如果與 A 不同，則 --A。遍歷結(jié)束時，A 就是結(jié)果。時間復(fù)雜度是 O(N)。但是當(dāng)數(shù)組中不存在次數(shù)大于一半的數(shù)時，這種方法找到的數(shù)還是不是正確的。
不過綜合起來看，如果默認一定存在出現(xiàn)次數(shù)大于一半的數(shù)，那么第三種方法是最好的，思路清晰，實現(xiàn)簡單。
下面是對第三種方法的實現(xià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) 編輯 收藏 引用