剑指offer28:找出数组中超过一半的数字。
2019-08-27 07:07:10来源:博客园 阅读 ()
剑指offer28:找出数组中超过一半的数字。
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 };View Code
(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 };View Code
(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 }View Code
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 }View Code
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
原文链接:https://www.cnblogs.com/wxwhnu/p/11415849.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 给定一个由 0 和 1 组成的矩阵,找出每个元素到最近的 0 的 2020-04-15
- 剑指offer笔记面试题1----赋值运算符函数 2019-10-18
- 剑指offer65:矩阵中的路径(二维数组,二分查找) 2019-09-02
- 剑指offer62:二叉搜索树的第k个结点,二叉搜索树【左边的元 2019-08-31
- 剑指offer59:按之字形顺序打印二叉树:[[1], [3,2], [4,5,6 2019-08-31
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash