欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

剑指offer28:找出数组中超过一半的数字。

程序员文章站 2022-06-20 18:35:53
1 题目描述 数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。 数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个 ......

1 题目描述

  数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。

2 思路和方法

  (1) 哈希表

  用哈希表记录每个元素出现的次数,如果该元素出现次数超过一半,返回1,时间复杂度o(n),空间复杂度o(n)。m[numbers[i]]+=1map<int, int> m;

  (2) 排序

  先排序,取中间的数,若这个数在数组中出现超过长度一半,则存在;否则不存在时间复杂度o(nlogn)排序;空间复杂度o(1).

  (3) 查找中位数 o(n)

  基于partiton函数 o(n),如果存在:该数出现次数超过一半,排序第2/n个元素是该元素;即为中位数

3 c++核心代码

(1)哈希表 m[numbers[i]]+=1map<intint> m;

 1 class solution {
 2 public:
 3     int morethanhalfnum_solution(vector<int> numbers) {
 4         // 哈希表存储某个数出现的次数 hash查询时间复杂度o(1);总时间复杂度o(n)
 5         map<int, int> m;
 6         for (int i = 0; i < numbers.size(); ++i) {
 7             m[numbers[i]]+=1;
 8             if(m[numbers[i]]>numbers.size()/2)
 9                 return numbers[i];
10         }
11         return 0;
12     }
13 };

(2) 排序

 1 class solution {
 2 public:
 3     int morethanhalfnum_solution(vector<int> numbers) {
 4         sort(numbers.begin(),numbers.end());
 5         int key = numbers[numbers.size()/2];
 6         int count = 0;
 7         for (int i = 0; i < numbers.size(); ++i) {
 8             if(key == numbers[i])
 9                 ++ count;
10         }
11         if (count>numbers.size()/2)
12             return key;
13         return 0;
14     }
15 };

(3)  查找中位数 o(n)——完整代码

 1 #include <iostream>
 2 int partition(int a[], int low, int high)
 3 {
 4     int pivot = a[low];
 5     while (low <high)
 6     {
 7         while (low<high && a[high] >= pivot) --high;
 8         a[low] = a[high];
 9         while (low<high && a[low] <= pivot) ++low;
10         a[high] = a[low];
11     }
12     a[low] = pivot;
13     return low;
14 }
15 int halfdata(int a[], int len)
16 {
17     int start = 0;
18     int end = len - 1;
19     int middle = len >> 1;
20     int index = partition(a, start, end);
21 
22     while (index != middle)
23     {
24         if (index > middle)
25         {
26             end = index - 1;
27             index = partition(a, start, end);
28         }
29         else
30         {
31             start = index + 1;
32             index = partition(a, start, end);
33         }
34     }
35     return a[index];
36 }
37 int main()
38 {
39     int a[9] = { 1, 2, 3, 2, 2, 2, 5, 4, 2 };
40     int len = 9;
41     int result = halfdata(a, 9);
42     printf("result:%d\n", result);
43 
44     system("pause");
45     return 0;
46 }

4 c++完整代码  

 1 #include <iostream>
 2 #include <vector>
 3  
 4 using namespace std;
 5  
 6 int morethanhalfnum(vector<int> numbers) 
 7 {
 8     if (numbers.size() == 0)
 9     {
10         return 0;
11     }
12  
13     int target = numbers[0];
14     unsigned int cnt = 1;
15     
16     for (unsigned int i = 1; i < numbers.size(); ++i)
17     {
18         if (target == numbers[i])
19         {
20             cnt++;
21         }
22         else
23         {
24             cnt--;
25         }
26  
27         if (cnt == 0)
28         {
29             cnt = 1;
30             target = numbers[i];
31         }
32     }
33     cnt = 0;
34     for (unsigned int i = 0; i < numbers.size(); ++i)
35     {
36         if (target == numbers[i])
37         {
38             cnt++;
39         }
40     }
41  
42     if (cnt * 2 > numbers.size())
43     {
44         return target;
45     }
46  
47     return 0;
48 }
49  
50 int main(void)
51 {
52     int a[] = {1,2,2,2,3,4,2,5,2};
53     vector<int> v(a, a + 9);
54  
55     cout<<morethanhalfnum(v)<<endl;
56     
57     return 0;
58 }

https://blog.csdn.net/u013575812/article/details/50130307

  时间复杂度o(n)。初始认为数组第一个数就是目标数(target)。之后遍历数组后面的元素,如果等于目标数,计数++; 否则计数--;如果发现目标数的计数<=0 说明当前目标数并不是最终的输出结果。更新目标数为当前遍历到的元素。遍历完数组所有元素之后 验证一下结果即可。

参考资料

https://blog.csdn.net/zjwreal/article/details/88607992

https://blog.csdn.net/u013575812/article/details/50130307