方法一：Boyer-Moore 投票算法
如果我们把众数记为 +1，把其他数记为 ?1，将它们全部加起来，显然和大于 0，从结果本身我们可以看出众数比其他数多
class Solution
{
public:
int majorityElement(vector<int>& nums)
{
int tmp = -1;
int count = 0;
for (auto& x : nums)
{
if (x == tmp)
{
++count;
}
else if(--count<0)
{
tmp = x;
count = 1;
}
}
return tmp;
}
};
int main()
{
Solution A;
vector<int> vec{ 2,2,1,1,1,2,2 };
cout << A.majorityElement(std::ref(vec)) << endl;
return 0;
}
时间复杂度：O(n)，Boyer-Moore 算法只对数组进行了一次遍历
空间复杂度：O(1)，Boyer-Moore 算法只需要常数级别的额外空间
方法二：排序
如果将数组 nums 中的所有元素按照单调递增或单调递减的顺序排序，那么下标为 n/2 的元素（下标从 0 开始）一定是众数
class Solution
{
public:
int majorityElement(vector<int>& nums)
{
sort(nums.begin(), nums.end());
return nums[nums.size() / 2];
}
};
int main()
{
Solution A;
vector<int> vec{ 2,2,1,1,1,2,2 };
cout << A.majorityElement(std::ref(vec)) << endl;
return 0;
}
时间复杂度：O(nlogn)。将数组排序的时间复杂度为 O(nlogn)
空间复杂度：O(logn)。如果使用语言自带的排序算法，需要使用 O(logn) 的栈空间，如果自己编写堆排序，则只需要使用 O(1) 的额外空间
