LeetCode 169 Majority Element

LeetCode 169 Majority Element

可以先排序，再return中位数，但估计这种方法不会被面试官认可。

这里用到了Moore’s voting algorithm  http://www.cs.utexas.edu/~moore/best-ideas/mjrty/example.html

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

另一种方法：

随机选择一个数，判断是否是最多的。由于一定存在一个数量大于2/n的数，所以这种方法运行时间很短

int majorityElement(int* nums, int numsSize) {
    while (1)
    {
        int idx = rand() % numsSize;
        int candidate = nums[idx];
        int counts = 0; 
        for (int i = 0; i < numsSize; i++)
            if (nums[i] == candidate)
                counts++; 
        if (counts > numsSize / 2) return candidate;
    }
}