来刷题啊 2.17

LeetCode

169. Majority Element

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.

【思路】
因为出现最多的数的个数一定超过一半，那么可以发现，每次拿掉数组里面的任意两个不一样的数，剩下的那个就一定是出现最多的了。比如：1 1 1 1 2 3 4，每每拿掉任意两个不一样的，剩下的都会是1。
用栈来模拟这个拿掉的过程，则有如下对策：

1. 栈为空，入栈
2. 栈顶元素和我手上这个一致，入栈
3. 栈顶元素和我手上这个不一致，出栈

【代码】

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

【改进】
现在的空间复杂度是O(n)，然而其实可以降到O(1)，因为最终栈中剩下的那些只可能是一堆一毛一样的数字。
也即不用栈来保存，而是拿一个cand来保存那个可能的最终值和一个count来计数就好了。

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

【话痨】
打这题最迷的一点就是，我忘惹咋判栈空？？？在那里stack[0]==null? -1? -10086???的来了一圈，才看到别人打的是top = -1才想起来...
以及初始化 a[numsSize] 的时候，如果直接 a[numsSize] = {-10086} 这样在LeetCode上会报错，只能使用memset，似乎是跟编译器（C99）有关