在已排序数组中查找出现最多的数字
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 阅读(1128)
评论(0) 编辑 收藏 引用