【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清零时，取当前数作为resultelse count–;}return result;}};

当世界给草籽重压时，它总会用自己的方法破土而出。