剑指offer面试题29~数组中出现次数超过一半的数字
一.问题描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
二.问题分析
刚开始看到这道问题的时候，我就想如果这个数组是有序的就好了，那仫在一个数组中出现次数超过数组长度一半的数字一定是中间的那个数字了(至于为什仫读者自行脑补吧！！！)。但是这种排序之后再返回中位数的方法的时间复杂度在最好的情况下只有O(n*lgn)(在八大排序算法中时间复杂度最好的只有O(n*lgn))，而且也未用到这个数组的特性。
-
1.基于快速排序的O(n)的方法
对于快速排序相信大家都不陌生，利用快排它的主要思想是这样的：先选取一个数字做key，经过一趟快速排序之后在key左边的数字一定比key小，在key右边的数字一定比key大，如果选中的key正好是mid(mid=sz >> 1)则这个数字就是满足题意的数字；如果key的下标大于mid，则在key的左边查找；如果key的下标小于mid则在key的右边继续查找，直到找到满足题意要求的数字。。。
class Solution {
public:
int PartSort(vector<int> numbers,int start,int end)
{
int left=start;
int right=end;
int key=numbers[end];
while(left < right)
{
//left找比key大的值，找到并交换
while(left < right && numbers[left] <= key)
{
left++;
}
swap(numbers[left],numbers[right]);
//right找比key小的值，找到并交换
while(left < right && numbers[right] >= key)
{
right--;
}
swap(numbers[right],numbers[left]);
}
numbers[left]=key;
return left;
}
int MoreThanHalfNum_Solution(vector<int> numbers) {
if(numbers.size() <= 0){ //数组是否合法
return 0;
}
int sz=numbers.size();
int start=0;
int end=sz-1;
int mid=sz>>1;
int index=PartSort(numbers,start,end);
while(index != mid)
{
if(index > mid)
{
end=index-1;
index=PartSort(numbers,start,end);
}
else{//index <= mid
start=index+1;
index=PartSort(numbers,start,end);
}
}
int ret=numbers[mid];
int count=0;
//统计中位数出现的次数
for(int i=0;i<sz;i++)
{
if(ret == numbers[i])
count++;
}
if(2*count <= sz){
return 0;
}
else{
return ret;
}
}
};在实现并在线通过了上述代码之后这道题仫是否其他的解法呢？答案是肯定的。。。
-
2.保存数字和次数的方法O(n).
//result保存数字，count保存该数字出现的次数
//如果下一个数字和之前保存的数字相同则count++
//如果下一个数字和之前保存的数字不同则count–
//如果count==0，则修改result的值并将count置为1
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
if(numbers.size() <= 0){ //数组是否合法
return 0;
}
int result=numbers[0];
int sz=numbers.size();
int count=1;
for(int i=0;i<sz;i++)
{
if(count == 0)
{
result=numbers[i];
count=1;
}
else if(numbers[i] == result){
count++;
}
else{
count--;
}
}
//判断出现次数最多的数字的次数是否超过数组长度的一半
int times=0;
for(int i=0;i<sz;i++)
{
if(result == numbers[i])
{
times++;
}
}
if(2*times <= sz){
return 0;
}
else{
return result;
}
}
};