题目描述:
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。
#思路
因为元素出现的次数超过了一半,所以很明显,可以先排序,然后数组的中间的元素就是要找的出现超过一半的元素,然后进行检验,如果没有一半,则输出0。
#code
int MoreThanHalfNum_Solution(vector<int> numbers) {
if(numbers.size()==0)
return 0;
sort(numbers.begin(),numbers.end());
int num=numbers[numbers.size()/2];
int count=0;
for(int i=0;i<numbers.size();i++)
{
if(num==numbers[i])
count++;
}
if(count>=(numbers.size()/2+1))
return num;
return 0;
}
#思路
已经说过了,上面那个是ologn的,可以将复杂度降低到n,怎么做呢,很简单,因为如果满足条件的元素存在,那么它的出现次数肯定是大于一半的,无论对于奇数个数数组还是偶数个数数组来说,出现次数大于一半,那么它都比其它元素出现的次数加起来还要多,所以设置两个值,一个用来保存数组中的值,一个用来保存次数。
然后如果下一个遍历到的数字与之前保存的数字相同,那么次数加一,否则次数减一,当次数为0的时候,保存当前遍历到的数字,将count置为1,如果存在满足条件的数字,那么最后可你的那个是该数字将count置为1,只需要检验count是否为1,不为1,输出0,为一继续进行检验,看该元素是否满足条件,满足则输出该数字,不满足输出0。
#code
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
if(numbers.size()==0)
return 0;
int num=numbers[0];
int count=1;
for(int i=1;i<numbers.size();i++)
{
if(count==0)
{
num=numbers[i];
count++;
}
else
{
if(num==numbers[i])
count++;
else
count--;
}
}
if(count==0)
return 0;
else
{
count=0;
for(int i=0;i<numbers.size();i++)
{
if(num==numbers[i])
count++;
}
if(count>=(numbers.size()/2+1))
return num;
return 0;
}
return 0;
}
};
#思路
第三种则是利用快排的思想,如上面所说,出现次数超过一半,肯定是中位数,根据快排的思想,随机选择一个数,比它大的放在右边,比它小的放在左边,那么如果选中的数字刚好下标为n/2,那么肯定就是要找的中位数,如果下标小于n/2,那么往右边接着寻找,否则往左边接着寻找,利用一个递归的过程,肯定是可以找到n/2下标这个元素的,而且它的速度肯定要比全部排好序更快,然后将下标为n/2的元素作为结果进行检验。
#code
class Solution {
public:
int slecet(vector<int>&a,int l,int r)
{
int mid=l+((r-l)>>1);
if ( a[ l ] > a[ mid ] )
swap( a[ l ], a[ mid ] );
if ( a[ l ] > a[ r ] )
swap( a[ l ], a[ r ] );
if ( a[ mid ] > a[ r ] )
swap( a[ mid ], a[ r ] );
/* A[ Left ] <= A[ Center ] <= A[ Right ] */
swap( a[ mid ], a[ r-1 ] ); /* 将pivot藏到右边,节约一次比较,反正都比过了 */
/* 只需要考虑 A[ Left+1 ] … A[ Right–2 ] */
return a[ r-1 ]; /* 返回 pivot */
}
int partition(vector<int>&a,int l,int r,int mid)
{
if(l>=r)
return mid;
if(r-l==1)//一定要加上这一个判断条件,因为我们用了slecet函数选择元素,会导致只有两个元素的时候归并失效。
{
if(a[r]>=a[l])
return mid;
else
swap(a[l],a[r]);
return mid;
}
int num=slecet(a,l,r);
int i=l+1;
int j=r-2;
while(i<j)
{
while(i<j&&a[i]<=num)//
i++;
while(j>i&&a[j]>=num)//可以往
j--;
if(i<j)
{
swap(a[i],a[j]);
}
else
break;
}
swap(a[r-1],a[i]);
return i;
}
int MoreThanHalfNum_Solution(vector<int> numbers) {
if(numbers.size()==0)
return 0;
int mid=numbers.size()>>1;
int start=0;
int end=numbers.size()-1;
int index=partition(numbers,start,end,mid);
while(index!=mid)
{
if(index>mid)
{
end=index-1;
index=partition(numbers,start,end,mid);
}
else
{
start=index+1;
index=partition(numbers,start,end,mid);
}
}
int num=numbers[mid];
int count=0;
for(int i=0;i<numbers.size();i++)
{
if(num==numbers[i])
count++;
}
if(count>=(numbers.size()/2+1))
return num;
return 0;
}
};
如果觉得《剑指offer数组中出现次数超过一半的数字》对你有帮助,请点赞、收藏,并留下你的观点哦!