[编程题]数组中出现次数超过一半的数字
论文问答
1
给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。
数据范围：n≤50000n \le 50000n≤50000，数组中元素的值 0≤val≤100000 \le val \le 100000≤val≤10000
要求：空间复杂度：O(1)O(1)O(1)，时间复杂度 O(n)O(n)O(n)
输入描述:
保证数组输入非空，且保证有解
示例1
输入
[1,2,3,2,2,2,5,4,2]
输出
2
-
思路一： 数组排序后，如果符合条件的数存在，则一定是数组中间那个数 。（比如：1，2，2，2，3；或2，2，2，3，4；或2，3，4，4，4等等）
这种方法虽然容易理解，但由于涉及到快排sort，其时间复杂度为 O(NlogN) 并非最优；
参考代码如下：
class Solution { public: int MoreThanHalfNum_Solution(vector<int> numbers) { // 因为用到了sort，时间复杂度O(NlogN)，并非最优 if(numbers.empty()) return 0; sort(numbers.begin(),numbers.end()); // 排序，取数组中间那个数 int middle = numbers[numbers.size()/2]; int count=0; // 出现次数 for(int i=0;i<numbers.size();++i) { if(numbers[i]==middle) ++count; } return (count>numbers.size()/2) ? middle : 0; } };
发表回复