剑指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]]+=1;
map<int, int> m;
(2) 排序
先排序,取中间的数,若这个数在数组中出现超过长度一半,则存在;否则不存在时间复杂度o(nlogn)排序;空间复杂度o(1).
(3) 查找中位数 o(n)
基于partiton函数 o(n),如果存在:该数出现次数超过一半,排序第2/n个元素是该元素;即为中位数
3 c++核心代码
(1)哈希表 m[numbers[i]]+=1;
map<int, int> 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
上一篇: jQuery选择器之id选择器使用介绍
下一篇: 2014愚人节必备qq空间整人留言
推荐阅读
-
剑指offer28:找出数组中超过一半的数字。
-
PHP实现找出数组中出现次数超过数组长度一半的数字算法示例
-
【剑指 Offer-python】 03. 数组中重复的数字
-
剑指offer 56 数组中数字出现的次数 lintcode 82. 落单的数、83. 落单的数 II、84. 落单的数 III
-
【剑指offer】面试题56(1):数组中只出现一次的两个数字
-
剑指offer:数组中只出现一次的两个数字(java版)
-
剑指offer 面试题56 python版+解析:数组中只出现一次的两个数字,数组中唯一只出现一次的数字
-
剑指offer第二版-56.数组中只出现一次的两个数字
-
【算法分享】剑指offer56-数组中只出现一次的两个数字
-
剑指 Offer 56 - I. 数组中只出现一次的两个数字