题目描述
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。
思路一:排序
如果数组中有出现次数超过一半的数字,那么排序之后取数组中间元素肯定就是数组中超过一半的数字。
class Solution
{
public:
int MoreThanHalfNum_Solution( vector<int> number )
{
int size = number.size();
vector<int> number_dup( number ); //不破坏原始数组
sort( number_dup.begin(), number_dup.end() ); //排序所需时间复杂度为O(nlog(n))
int result = number_dup[size/2];
bool isMoreHalf = checkMoreThanHalf( number_dup, result );
if ( isMoreHalf )
return result;
return 0;
}
private:
//判断target是不是number中出现次数超过一半的数字
bool checkMoreThanHalf( vector<int>& number, int target )
{
int times = 0;
int size = number.size();
for ( int i = 0; i < size; i++ )
{
if ( number[i] == target )
times++;
}
if ( times > size/2 )
return true;
else
return false;
}
};
思路二:基于partition函数
这里的partition函数来自于随机快排,partition函数每次都会在数组中随机选择一个哨兵元素,并且将数组中所有小于该哨兵的元素放到左边,将所有大于该哨兵的元素放到右边,最后会找到该哨兵元素在数组中排好序的位置。数组中超过一半的数字如果有肯定会出现在数组中间位置,所以只需要使用partition函数找到排序后处于数组中间位置的元素。
值得说明的是partition函数的时间复杂度为O(n),因此采用partition函数的时间效率会比直接排序高。
int MoreThanHalfNum_Solution( vector<int> number )
{
int middle = number.size()/2;
int index = partition( number, 0, number.size() );
int start = 0, end = number.size()-1;
while ( index != middle )
{
//找到的元素位置超过中间位置,继续在前半部分找
if ( index > middle )
end = index;
//找到的元素位置没有达到中间位置,继续在后半部分找
else
start = index + 1;
index = partition( number, start, end );
}
int result = number[middle];
cout << "result:" << result << endl;
bool isMoreHalf = checkMoreThanHalf( number, result );
if ( isMoreHalf )
return result;
return 0;
}
//在[start, end)这个区间中选择一个元素,将其放置到正确的位置上,并且返回这个位置的下标
int partition( vector<int>& number, int start, int end )
{
int index = randomRange( start, end );
cout << "index:" << index << endl;
int sentry = number[index];
end--;
while ( start < end )
{
if ( number[start] <= sentry )
{
start++;
continue;
}
if ( number[end] > sentry )
{
end--;
continue;
}
swap( &number[start], &number[end] );
start++;
end--;
}
swap( &number[end], &number[index] );
return end;
}
void swap( int* a, int* b )
{
int temp = *a;
*a = *b;
*b = temp;
}
//产生[start, end)之间的一个随机数
//使用c语言中的random函数
int randomRange( int start, int end )
{
int result = (int)random()%(end-start)+start;
return result;
}
思路三:数组特点
数组中一个数字出现的次数比其他数字出现次数的总和还多。则可以设置两个变量,一个保存数组中的一个数字,一个保存次数,当本次遍历的数字和我们保存的数字相同时,将次数加1,否则减1。如果次数变为0,我们需要重新保存当前数字,并且把次数设置为1.这样要找的数字肯定是最后一个把次数设为1的那个数字。
时间复杂度O(n)
int MoreThanHalfNum_Solution( vector<int> number )
{
int store = number[0];
int match = 1;
for ( int i = 1; i < number.size(); i++ )
{
if ( match == 0 )
{
store = number[i];
match = 1;
}
else if ( store == number[i] )
match++;
else
match--;
}
bool isMoreHalf = checkMoreThanHalf( number, store );
if ( isMoreHalf )
return store;
return 0;
}