题目：

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

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

示例 1:

输入: [3,2,3] 输出: 3 示例 2:

输入: [2,2,1,1,1,2,2] 输出: 2

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/majority-element 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

（面试题）

数组中占比超过一半的元素称之为主要元素。给定一个整数数组，找到它的主要元素。若没有，返回-1。

示例 1：

输入：[1,2,5,9,5,9,5,5,5] 输出：5  

示例 2：

输入：[3,2] 输出：-1  

示例 3：

输入：[2,2,1,1,1,2,2] 输出：2  

说明： 你有办法在时间复杂度为 O(N)，空间复杂度为 O(1) 内完成吗？

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/find-majority-element-lcci 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

结果：

方法一：排序后取中

方法二：摩尔算法

解题思路：

方法一：排序取中

因为求的多数是大于numsSize/2的，所以排序后中间那个数必定就是。

方法二：摩尔算法

如果当前数和记录数一样，则sum+1，如果不一样就-1，当sum变成0，则记录数改成下一个数。因为必定大于numsSize/2，所以一一配对后，必定大于0.

代码：

方法一：排序取中：

int compar(const void *a, const void *b) { return *(int *)a - *(int *)b; } int majorityElement(int* nums, int numsSize){ qsort(nums, numsSize, sizeof(int), compar); return nums[numsSize/2]; }

方法二：摩尔算法：

int majorityElement(int* nums, int numsSize){ int sum = 1; int num = nums[0]; for(int i = 1; i < numsSize; i++) { if(nums[i] == num) { sum++; } else { sum--; } if(sum == 0) { num = nums[i + 1]; } } return num; }