面试题29：数组中出现次数超过一半的数字

时间：2022-12-01 11:02:40

题目：数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。


1)      第一种方法,时间复杂度为O(n)，此方法会改变数组元素的位置

快速排序中有一个步骤是找出一个数，将大于这个数的数字放在这个数字右边，小于这个数字的放在这个数字的左边，这个数字在排序的数组中位置就找到了，第一种方法使用这个思路查找位于中间位置的数字，因为数字出现次数超过了数组长度的一般，所以中间位置的数字一定是要找的数字。

#include <iostream>
#include<time.h>
#include<stdlib.h>/*用到了srand函数，所以要有这个头文件*/
using namespace std;

//为了区分是函数返回0还是输入不合法返回0设置一个变量判断
bool inputInvalid=false;

int Partition(int * data,int length,int start,int end);
int randomInRange(int start, int end);
void swap(int * a,int * b);
bool CheckInvalidArray(int * numbers,int length);
bool CheckMoreThanHalf(int * numbers,int length,int number);


int MoreThanHalfNum(int * numbers,int length)
{
if(CheckInvalidArray(numbers,length))
return 0;

int start=0;
int end=length-1;
//中位数下标
int middle=length>>1;
//按随机生成的下标将大于此下标位置的数的元素放右边，小于的放左边，并返回下标给index
int index=Partition(numbers,length,start,end);
//寻找中位数
while(index!=middle)
{
//如果index小于Middle说明中位数应该在index之后
if(index<middle)
{
start=index+1;
//从index之后再寻找
index=Partition(numbers,length,start,end);
}
else
{
end=index-1;
index=Partition(numbers,length,start,end);
}
}
int result=numbers[middle];

if(!CheckMoreThanHalf(numbers,length,result))
return 0;
return result;
}

//快速排序中随机生成一个数字，将此大于此下标位置的数的元素放右边，小于的放左边
int Partition(int * data,int length,int start,int end)
{
if(data==NULL||length<=0||start<0||end>=length)
{
throw new exception("invalid parameters");
}

//在起始位置和结束位置中随机生成一位数
int index=randomInRange(start,end);
//将index位置的数和最后一位交换，放置最后
swap(&data[index],&data[end]);
int small=start-1;
//遍历数组
for(index=start;index<end;index++)
{
if(data[index]<data[end])
{
/*
如果当前数小于分界元素，small++，和index相等，指向当前元素，向后遍历
遇到大于分界元素的，small不变，
直到遇到下一个小于分界元素的，对small再加1，
此时small记录的就是第一个大于分界元素的元素下标，然后交换值
*/
small++;
//如果small不指向当前位置
if(index!=small)
{
//交换当前元素和small位置的元素
swap(&data[index],&data[small]);
}
}
}

++small;
swap(&data[small],&data[end]);
return small;//返回下标
}

//生成随机数
int randomInRange(int start, int end)  
{  
    srand(time(NULL));  

    return start + rand()%(end-start+1);  
}
//交换两个数的值
void swap(int * a,int * b)
{
int temp=*a;
*a=*b;
*b=temp;
}

//检验数组是否为空或者长度小于0
bool CheckInvalidArray(int * numbers,int length)
{
inputInvalid=false;
if(numbers==NULL||length<=0)
{
inputInvalid=true;
}
return inputInvalid;
}

//检验数组是否符合要求（出现次数最多的超过长度一半）
bool CheckMoreThanHalf(int * numbers,int length,int number)
{
int times=0;
for(int i=0;i<length;i++)
{
if(numbers[i]==number)
times++;
}
bool isMoreThanHalf=true;
if(times*2<=length)
{
inputInvalid=true;
isMoreThanHalf=false;
}
return isMoreThanHalf;
}
int main()
{
int arr[]={1,1,3,5,1,1};
int result=MoreThanHalfNum(arr,6);
cout<<result<<endl;
return 0;
}


1)      第二种方法，时间复杂度为O(n)

遍历数组，在遍历数组的过程中保存两个值，一个数数组中的一个数字，一个是次数，遍历下一个数字的时候和之前保存的数字比较，如果相同次数加1，如果不同次数减一，如果次数变为0就将保存的数字数设置为当前数字，遍历结束保存的数字就是要找的那个数字。

int MoreThanHalfNum(int * numbers,int length)
{
    if(CheckInvalidArray(numbers,length))
return 0;

int result=numbers[0];
int times=1;
for(int i=0;i<length;i++)
{
if(times==0)
{
result=numbers[i];
}
else if(result==numbers[i])
{
times++;
}
else
{
times--;
}
}


if(!CheckMoreThanHalf(numbers,length,result))
return 0;
return result;
}

//检验数组是否为空或者长度小于0
bool CheckInvalidArray(int * numbers,int length)
{
inputInvalid=false;
if(numbers==NULL||length<=0)
{
inputInvalid=true;
}
return inputInvalid;
}

//检验数组是否符合要求（出现次数最多的超过长度一半）
bool CheckMoreThanHalf(int * numbers,int length,int number)
{
int times=0;
for(int i=0;i<length;i++)
{
if(numbers[i]==number)
times++;
}
bool isMoreThanHalf=true;
if(times*2<=length)
{
inputInvalid=true;
isMoreThanHalf=false;
}
return isMoreThanHalf;
}



标签：

相关文章