/*
Author: Zoro
Date:   2019/11/10
Function:   Majority Element
Title:  leetcode 169

think:  出现的次数最多，且大于数组的二分之一
        两种方法：统计方法，数据结构法
        1: 空           入栈
        2: 栈顶 = 元素  入栈
        3: 其它情况     出栈
majority.c
时间复杂度: O(n)
空间复杂度: O(n)
*/
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int majorityElement(int* nums, int numsSize) {

    int* stack = malloc(sizeof(int) * numsSize);
    int top = -1;
    int i;

    for (i=0; i<numsSize; i++) {
        if (top == -1) {
            stack[++top] = nums[i];
        }
        else if (stack[top] == nums[i]) {
            stack[++top] = nums[i];
        }
        else {
            top--;
        }
    }
    return stack[0];
}

int main() {

    int nums[] = {1, 2, 1, 1, 2, 3, 1};
    int result = majorityElement(nums, 7);
    printf("result = %d\n", result);
    return 0;

}

时间复杂度: O(n)
空间复杂度: O(1)
int cand;
int count = 0;

for (i=0; i<numsSize; i++) {
    if (count == 0) {
        cand = nums[i];
        count++;
    } 
    else if (cand == nums[i]) {
        count++;
    }
    else {
        count--;
    }
    return cand;
}