【LeetCode】Majority Element两种做法对比

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
思路很简单，先排序，然后在中间的一定是出现最多的。为什么呢？因为它出现more than n/2次，所以它前后元素一定不会超过n/2个。排序采取了快排，好久没写还有点生疏了。但是这个做法却LTE了，尴尬。。
代码

class Solution {
public:
    int majorityElement(vector<int> &num) {
        int len = num.size();
        quickSort(num,0,len-1);
        return num[len/2];
    }
    void quickSort(vector<int> &num,int low,int high){
        if (low>=high) return;
        int i=low;int j=high;
        int pivot = num[i];
        while (i<j){
            while (i<j&&num[j]>=pivot){j--;}
            num[i]=num[j];
            while (i<j&&num[i]<=pivot){i++;}
            num[j]=num[i];
        }
        num[i]=pivot;
        quickSort(num,low,i-1);
        quickSort(num,i+1,high);

    }
};

做法2
思路：既然最多元素出现了n/2次，那我就想用抵消的思想，用它和与它不相等的元素一一相消，剩下的一定就是最多的那个元素。根据这个想法，有了如下代码。

class Solution {
public:
    int majorityElement(vector<int> &num) {
        int result=num[0];int len = num.size();
        int count = 0;
        for (int i=0;i<len;i++){
            if (count==0||result==num[i]) {
                result = num[i];count++;}   //count清零时，取当前数作为result
            else count--;
        }
        return result;
    }
};