leetcode-169-Majority Element
题目描述：
Given an array of sizen, find the majority element. The majority element is the element that appearsmore than⌊ n/2 ⌋times.
You may assume that the array is non-empty and the majority element always exist in the array.
要完成的函数：
int majorityElement(vector<int>& nums)
说明：
1、这道题目给定长度为n的数组，要求输出某个元素的值，该元素出现次数超过⌊n/2⌋。
2、不得不说，这道题目有很多种解法，最暴力的莫过于双重循环，统计各个元素的出现次数，统计到出现⌊n/2⌋次的就停止，然后输出。
3、但除此之外，我们还可以尝试快速排序，排序完数组中坐标为⌊n/2⌋的就是我们要输出的元素。快排代码如下：
#include<algorithm>
int majorityElement(vector<int>& nums)
{
sort(nums.begin(),nums.end());
return nums[nums.size()/];
}sort是头文件<algorithm>中的函数，采用的是类似于快排的方法，该函数一共有三个参数。
第一个参数是数组指针，第二个参数是数组中最后一项的下一项的指针。
最后一个参数是排序方法，可以使用c++内置的比较函数。记得要include<funtional>，然后less<int>()表示从小到大排序，这也是默认排序方法，还可以是greater<int>()，从大到小排序。
最后一个参数还可以是自定义函数，如下是从大到小的排序：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool compare(int a,int b)//自定义比较函数
{
return a>b;
}
int main()
{
vector<int>v={,,,,,,,,};
sort(v.begin(),v.end(),compare);//以函数名作为第三个参数，进行快排
for(vector<int>::iterator iter=v.begin();iter<v.end();iter++)//vector迭代器的使用
cout<<*iter<<" ";
return ;
}快排算法beats 20% of cpp submissions
4、对3中的算法做些优化，我们是否可以只做几遍快速排序，当得到⌊n/2⌋位置的最终值时就停下呢？（我们知道快排每一遍排序都可以得到一个最终值）这样我们可以大大减少所需要的时间。
刚好c++中有nth_element函数，代码如下：
int majorityElement(vector<int>& nums)
{
nth_element(nums.begin(),nums.begin()+ nums.size()/, nums.end());//这个函数进行部分快排，直到第二个参数表示的位置已经得到最终值
return nums[nums.size()/];
}nth_element原理如下：
首先选定一个基准值，比如我们常用的nums[0]，进行第一次快排，nums[0]的值最终放到了mid位置上，这时候mid左边的值都比它小，右边的值都比它大。
接着看一下第二个参数表示的位置的值在mid的哪一边，然后对这一边继续进行快排，mid的另一边就不理了。
重复操作，直到第二个参数表示的位置的值成为最终值。
这种算法beats 79.89% of cpp submissions
5、上面我们一共说了三种算法，暴力双重循环，快排，部分快排。除此之外，在评论区还见到了其他三种惊为天人的算法，下面逐一与大家分享。
6、随机算法
代码如下，应该不难看懂~
#include<ctime><br />int majorityElement(vector<int>& nums)
{
int n = nums.size();
srand(unsigned(time(NULL)));//以当前时间作为一个种子，NULL表示产生的时间值不被计算机存储，只被当前语句处理。生成的值要转化为unsigned int类型作为srand的参数。
while (true)
{
int idx= rand() % n;
int candidate = nums[idx];
int counts = ;
for (int i = ; i < n; i++)
if (nums[i] == candidate)
counts++;
if (counts > n / ) return candidate;
}
}这个算法虽然最差时间复杂度是无穷大，但是实际过程中由于我们要找的数占据了数组的一半以上，所以随机生成这个数的概率还是很高的。
实测了五次，最好的是beat 97.24% of cpp submissions，最差的是11.17% of cpp submissions。
这种做法还是挺新鲜的，碰到做不出的题目也可以用这种方法水过题目测试点。
7、成对抵消算法
先附上代码，很简洁的~
int majorityElement(vector<int>& nums) <br />{
int major, counts = , n = nums.size();
for (int i = ; i < n; i++) <br /> {
if (!counts) //如果counts为0则改变major值，同时赋counts为1<br /> {
major = nums[i];
counts = ;
}
else counts += (nums[i] == major) ? : -;
}
return major;
}由于数组中，我们要找的元素出现了⌊n/2⌋次，因此我们可以，从数组中找出能成对抵消的元素，抵消到最后剩下的那一个就是我们要找的数了。
例如：数组为[2,1,2,3,2]
第一次循环，major=2，counts=1
第二次循环，counts=0
第三次循环，major=2，counts=1
第四次循环，counts=0
第五次循环，major=2，counts=1
最后的major就是我们要的数。
再举一个例子，数组为[3,3,1,3,1]
第一次循环，major=3，counts=1
第二次循环，counts=2
第三次循环，counts=1
第四次循环，counts=2,
第五次循环，counts=1
因为counts不会退到0，所以major也就不会改变，最后输出major=3
这种算法时间复杂度为O(n)，是一种极为简单而又精彩的做法。
实测beats 79.89% of cpp submissions。
8、位操作算法
看到discuss区中大神提出了7中的成对抵消算法，笔者就想起了前几天做过的异或题目，相同的值可以抵消，但是这道题并不是相同值抵消，而是不同值，所以不能使用异或~
但是我们仍然可以使用位操作来完成这道题目。
我们要找的数出现了⌊n/2⌋次以上，从二进制的角度来看，也就是32位中的某一位出现了⌊n/2⌋次以上，根据这一点我们可以采取如下操作
int majorityElement(vector<int>& nums)
{
int major = 0, n = nums.size();
for (int i = 0, mask = 1; i < 32; i++, mask <<= 1)
{
int bitCounts = 0;
for (int j = 0; j < n; j++)
{
if (nums[j] & mask) //在mask代表的这一位上为1<br /> bitCounts++;
if (bitCounts > n / 2) //总的出现次数在n/2以上，则我们要找的数在这一位上有出现，major要“或”上这一位
{
major |= mask;
break;//跳出内层循环
}
}
}
return major;
}总结：
这虽然是一道简单的题目，但发散开来，我们可以总结出这么多种方法：
1、暴力双重循环法
2、快排
3、部分快排
4、随机算法
5、成对抵消算法
6、位操作法
其中的成对抵消算法最稳定，结果也优秀。
部分快排结果也挺优秀，不过花费的时间不会很稳定。
随机算法成绩可以很优秀，也可以很糟糕，实际体验就看命了，不过好处就是很简单地解出一些题目，trick。
快排时间复杂度高一点，传统解法。
暴力双重循环是最简单但是也最高时间复杂度的解法。
位操作也是双重循环，跟暴力解法差不多。
笔者还是最喜欢成对抵消的做法，简单稳定~
这道题目还有其他算法，由于时间关系就不介绍了，详见以下两个网址：
https://leetcode.com/problems/majority-element/discuss/51612/6-Suggested-Solutions-in-C++-with-Explanations
https://leetcode.com/problems/majority-element/solution/
本文章几种算法、思路和代码都来源于这两个网页介绍的内容。侵删。