给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：
输入：[3,2,3] 输出：3
示例 2：
输入：[2,2,1,1,1,2,2] 输出：2

进阶：

  • 尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

    摩尔投票

    思路：可以看做好几个不同军队抢夺一个高地，他们一对一消耗，因为有个军队超过了n/2，经过消耗后，他还有人活着。
    代码实现

    1. //摩尔投票
    2. int majorityElement(int* nums, int numsSize){
    3.   int key = nums[0];
    4.   int count = 0;
    5.   for (size_t i = 0; i < numsSize; i++)
    6.   {
    7.       if(nums[i] == key)
    8.           count++;
    9.       else
    10.           count--;
    12.       if(count <= 0)
    13.       {
    14.           key = nums[i+1];
    15.       }
    17.   }
    18.   return key;
    19. }

    使用栈

    1. //使用栈
    2. int majorityElement(int* nums, int numsSize){
    3. int *stack=malloc(sizeof(int)*numsSize);
    4.    int top=-1;
    5.    for(int i=0;i<numsSize;i++){
    6.        if(top==-1){
    7.            stack[++top]=nums[i];
    8.        }
    9.        else if(stack[top]==nums[i]){
    10.            stack[++top]=nums[i];
    11.        }
    12.        else top--;
    13.    }
    14.    return stack[0];
    15. }