题目

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

1
2
Input: [3,2,3]
Output: 3

Example 2:

1
2
Input: [2,2,1,1,1,2,2]
Output: 2

思路

本来想强行暴力,解决问题,但无奈时间超限

暴力法 run time error

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
   int *num= (int *) malloc(sizeof(int));
for (int i=0;i<numsSize;i++){
for(int j=0;j<numsSize;j++)
{
if(nums[i]==nums[j])
{
num[i]++;
} //end if
} //end for
}// end for
// 判断最大值输出
int max=0;
int imax=0;
for(int i=0;i<numsSize;i++)
{
if(max<num[i]) {
max = num[i];
imax = i;
}
}
return nums[imax];

时间简短版

1
2
3
4
5
6
7
8
9
int cmpfunc (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}
int majorityElement(int* nums, int numsSize) {
qsort(nums,numsSize,sizeof(int),cmpfunc);

return nums[numsSize/2];
}