首页 > 代码库 > 出现次数超过一半的数字
出现次数超过一半的数字
【问题】
题目:数组中有一个数字出现的次数超过了数组长度的一半,找出这个数字。
【分析】
解法1:
先排序,排序后数组中间的那个元素就是要找的那个数字。时间复杂度O(n*logn)。
解法2:
既要缩小总的时间复杂度,那么可以用查找时间复杂度为O(1)的hash表,即以空间换时间。哈希表的键值(Key)为数组中的数字,值(Value)为该数字对应的次数。然后直接遍历整个hash表,找出每一个数字在对应的位置处出现的次数,输出那个出现次数超过一半的数字即可。
解法3:
咱们根据数组的特性考虑到:
- 数组中有个数字出现的次数超过了数组长度的一半。换句话说,有个数字出现的次数比其他所有数字出现次数的和还要多。
- 因此我们可以考虑在遍历数组的时候保存两个值:一个是数组中的一个数字,一个是次数,当我们遍历到下一个数字的时候:
- 如果下一个数字和我们之前保存的数字相同,则次数加1;
- 如果下一个数字和我们之前保存的数字不同,则次数减1;当次数减到0,我们需要保存下一个数字,并把次数重新设为1。
【代码】
#include <stdio.h> #include <stdlib.h> int FindNumber1(int *a, int len)//解法3 { int i; int candidate = a[0]; int nTime = 1; for (i = 0; i < len; i++) { if (candidate == a[i]) nTime++; else nTime--; if (nTime == 0) { candidate = a[i]; nTime = 1; } } return candidate; } void q_sort(int *a, int start, int end) { int tmp = a[start]; int i = start, j = end; if (start + 1 > end) return; while (i < j) { while (i < j && a[j] > tmp) j--; if (i < j) a[i++] = a[j]; while (i < j && a[i] < tmp) i++; if (i < j) a[j--] = a[i]; } a[i] = tmp; q_sort(a, start, i - 1); q_sort(a, i + 1, end); } int FindNumber2(int *a, int len)//解法1 { q_sort(a, 0, len-1); return a[(len / 2)]; } int main(void) { int a[] = {0, 1, 1, 2, 1, 2, 2, 2, 2}; int len = sizeof(a) / sizeof(int); int res; res = FindNumber1(a, len); printf("%d\n", res); res = FindNumber2(a, len); printf("%d\n", res); return 0; }
出现次数超过一半的数字
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。