在已排序數組中查找出現最多的數字
http://www.vanjor.org/blog/2011/04/puzzle-array-find-most/
這里有個前提是數組已排好序
如果出現最多的數字出現次數大于一般，那么這個出現次數最多的數字就是位于數組中中間位置的數，這里需要考慮數組中的元素個數是奇數還是偶數
出現次數最多的數字的出現次數是大于元素數目的一般
如果數組是未排序的情況呢？
可以先把數組排好序，然后再把按照已排序的情況處理
也可以不排序，直接處理，這種情況下某個數的出現次數大于元素數目的一般比較好解決
1.
這里要解決的第一個問題是：
·已排序
·查找出現最多的數字，這個數字的出現次數不一定大于所有元素數目的一半
時間復雜度是 O(N)
程序：
1 #include <iostream>
2 #include <vector>
3 using namespace std;
4
5 bool isSorted(const vector<int>& data)
6 {
7 for (vector<int>::size_type i = 0; i != data.size() - 1; ++i)
8 {
9 if (data[i + 1] < data[i])
10 {
11 return false;
12 }
13 }
14 return true;
15 }
16
17 int findMaxTimesNumber(const vector<int>& data)
18 {
19 if (data.size() <= 0)
20 {
21 return -10000;
22 }
23 int count = 0;
24 int recorder = data[0];
25 int times = 1;
26 count = times;
27 for (vector<int>::size_type i = 1; i != data.size(); ++i)
28 {
29 if (data[i] == data[i - 1])
30 {
31 ++times;
32 }
33 else
34 {
35 if (times > count)
36 {
37 count = times;
38 recorder = data[i - 1];
39 }
40 times = 1;
41 }
42 }
43 if (times > count)
44 {
45 count = times;
46 recorder = data[data.size() - 1];
47 }
48 return recorder;
49 }
50
51 int main()
52 {
53 vector<int> data;
54 int n;
55 while (cin >> n)
56 {
57 data.push_back(n);
58 }
59 if (!isSorted(data))
60 {
61 cerr << "Error!" << endl;
62 return 1;
63 }
64 cout << findMaxTimesNumber(data) << endl;
65 }
===
這種解法本質上并不要求數組是已排好序的
只是要求相等的數字必須是在一起連續的
2.
第二種情況
數組是已排好序的，并且有一個數字出現次數大于數組中元素的總數目
時間復雜度：O(1)
如果總數目是奇數：
int foo(const vector<int>& data)
{
return data[data.size() / 2];
}
出現次數必須大于一半
如果總數目是偶數：
int foo(const vector<int>& data)
{
return data[data.size() / 2];
}
出現次數必須大于一半，其大小情況不必有嚴格要求，因為只要次數大于一半，該出現最多的數字一定是中間的那個 data[data.size() / 2]
3.
第三種情況
不是未排序的數組
但是有一個數字的出現次數大于數組元素數目的一半
時間復雜度：O(N)
1 #include <iostream>
2 #include <vector>
3 using namespace std;
4
5 int findMaxTimesNumber(const vector<int>& data)
6 {
7 if (data.size() <= 0)
8 {
9 return -10000;
10 }
11 int ret = data[0];
12 int count = 1;
13 for (vector<int>::size_type i = 1; i != data.size(); ++i)
14 {
15 if (data[i] == ret)
16 {
17 ++count;
18 }
19 else
20 {
21 --count;
22 if (count == 0)
23 {
24 count = 1;
25 ret = data[i];
26 }
27 }
28 }
29 if (count > 1)
30 {
31 return ret;
32 }
33 else
34 {
35 return -10000;
36 }
37 }
38
39 int main()
40 {
41 vector<int> data;
42 int n;
43 while (cin >> n)
44 {
45 data.push_back(n);
46 }
47 cout << findMaxTimesNumber(data) << endl;
48 return 0;
49 }
posted on 2011-12-29 12:29
unixfy 閱讀(1138)
評論(0) 編輯 收藏 引用