169.多数元素

给定一个大小为n的数组nums，返回其中的多数元素。多数元素是指在数组中出现次数大于n/2的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例一：

输入：nums = [3,2,3]

输出：3

示例二：

输入：nums = [2,2,1,1,1,2,2]

输出：2

算法思路：快速排序

解题思路

因为多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。所以对元素排序后，n/2一定是多数元素。

复杂度分析

N为数组长度

时间复杂度：O(N*logN)

空间复杂度：O(1)

int cmp (int*a,int*b)

{

    return *a-*b;

}

int majorityElement(int* nums, int numsSize){

    qsort(nums,numsSize,sizeof(int),cmp);

    return nums[numsSize/2];

}