leetcode 169 Majority Element
Given an array of size n, 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.
给定一个长为n的向量，要找到其中出现次数大于 ⌊ n/2 ⌋的元素，并输出它。在输入向量的时候要保证一定存在Majority Element，由于它的出现次数大于⌊ n/2 ⌋，则这种⌊ n/2 ⌋只有一个。
本题我选择的编程语言是C++，通过学习leetcode中关于本题的Discussion了解到本题可以通过如下几种方法来解：
Divide and Conquer（分治法）Hash Table（散列表）Sorting（排序）Randomization（随机化）Moore Voting AlgorithmBit manipulating下面我将逐个分析这些方法，及其实现代码。
分治法的思想是把一个大问题分解为多个和原问题相同的小问题，常常分解为两个小问题，算法采用递归的形式。本题将长为n的向量从中间截断为两个子向量，再分别找出两个子向量中的Majority Element，左边的子向量最大数为ml，右边子向量最大数mr，由于原向量的最大数必然是ml和mr中的一个（不然不满足最大数大于⌊ n/2 ⌋），所以假如ml=mr，则原向量最大数就为ml或mr；如ml！=mr，则遍历原向量，得到ml和mr出现次数，取大者。算法C++代码如下：
class Solution { public: int majorityElement(vector<int>& nums) { int n=nums.size(); int left=0; int right=n-1; int res=majority(left,right,nums); return res; } private: int majority(int left,int right,vector<int>& nums){ if(right==left) return nums[left]; int mid=(left+right)/2; int ml=majority(left,mid,nums); int mr=majority(mid+1,right,nums); if(ml==mr) return ml; else if(ml!=mr) { return (count(nums.begin()+left,nums.begin()+mid+1,ml)>count(nums.begin()+mid+1,nums.begin()+right+1,mr))?ml:mr; } } };
设算法时间消耗为T(n)，可以的得到递归式T(n)=2T(n/2)+O(n)，其中n是基数和偶数对时间复杂度没有影响，O(n)代表分治方法中分解与合并过程的消耗，具体而言，分解过程为：
int mid=(left+right)/2;合并过程为：
if(ml==mr) return ml; else if(ml!=mr) { return (count(nums.begin()+left,nums.begin()+mid+1,ml)>count(nums.begin()+mid+1,nums.begin()+right+1,mr))?ml:mr; } 可以看到，虽然当ml!=mr时，对ml和mr进行了遍历，但复杂度仅为O(n)。递归式T(n)=2T(n/2)+O(n)可以利用主方法来求解，主方法详见《算法导论》54页。所以T(n)=O(nlogn)。
此段代码中需要注意的C++知识有如下几点：
vector是一个类模板，vector表示对象的集合，称为容器，集合中所有对象类型相同，均有引用用于访问这些对象。类模板实例化需要指出实例化为什么样的类，如vector<int>、vector<Sales_item>。vector详见《C++ Primer》86页。 count函数为C++ STL（Standard Template Library)中的函数，count(begin,end,val)，用于返回一个计数器，指出val出现了多少次，beg和end为迭代器，beg指向容器第一个元素，end指向容器最后一个元素的下一个位置，它们可以由容器对象的成员函数begin()和end()得到。迭代器的知识详见《C++ Primer》95页。C++中引用必须初始化，且绑定对象不能再改变。引用只是绑定对象的别名，不会再分配空间。C++引用的绑定对象可以是内置基本类型，也可以是类类型。
本题Majority Element的个数大于⌊ n/2 ⌋，所以当对序列排好序后，下标为⌊ n/2 ⌋的元素一定为Majority Element。所以关键是对序列进行排序。C++代码如下：
class Solution { public: int majorityElement(vector<int>& nums) { int n=nums.size(); nth_element(nums.begin(),nums.begin()+n/2,nums.end()); return nums[n/2]; } }; 算法复杂度决定于采用的排序算法，一般能达到O(nlogn)，本算法中由于不需要使得下标为⌊ n/2 ⌋的元素前后的元素有序，所以可以采用STL中的nth_element(begin,begin+n,end)函数，使得序列中下标为n的元素为排序后相应序号的元素，之前的元素都比它小，但无序，之后的元素都比它大，但无序，这样时间复杂度比全排序要低。
随机化就是在算法中引入随机数，算法的行为不仅由输入决定，也由随机数生成器产生的数值决定。由于引入了随机数，所以没有一种输入会引起算法最坏的行为。随机算法能产生好的效果决定于输入的分布，这里Majority Element的个数大于⌊ n/2 ⌋就代表它的数量占比大于1/2。C++算法代码如下：
class Solution { public: int majorityElement(vector<int>& nums) { int n=nums.size(); int i; int candidate; int count; srand(unsigned(time(NULL))); while(1) { count=0; candidate=nums[rand()%n]; for(i=0;i<n;i++) { if(candidate==nums[i]) { count++; if(count>n/2) return candidate; } } } } };
此算法中决定时间复杂度的是while的循环次数，设这个次数为X，则它的期望E(X)<2。这个结果证明如下：
由于最大个数数占比大于1/2，所以第一次取到它所需次数的期望E(X)<E(Y)，其中Y为占比等于1/2时的期望。
所以E(X)<2，由于while循环中遍历一次的复杂度为O(n)，所以此随机算法的平均算法时间复杂度为O(n)。当然最坏情况是随机数生成器始终不能找到Majority Element，这时程序将无穷进行下去。
这个投票方法主要利用Majority Element大于一半这个特点，同一元素给自己投票，相依票数加一，遇到其他元素给它投票，票数减一，对于个数少于一半的元素，就算票数全部投给了自己，剩下大于一半的元素也会使得其票数到0；对于个数大于一半的元素，即使它给其他所有元素都投了反对票，也还会剩余正数张票。C++代码如下：
class Solution { public: int majorityElement(vector<int>& nums) { int n=nums.size(); int vote=1; int candidate=nums[0]; int i; for(i=1;i<n;i++) { if(nums[i]!=candidate) { vote--; if(vote==0) { candidate=nums[i]; vote=1; } } else vote++; } return candidate; } }; 代码中vote表示票数，当遍历到的数是目前的candidate时票数加1，否则票数减1，有上面分析可知，遍历完毕后vote一定大于0，且此时的candidate就为个数最大的元素，因为只进行了一次遍历，算法复杂度为O(n)。
这个算法从比特角度进行分析，由于vector中元素为int类型，共32bit，对于每一比特，序列中n个元素在这一bit上为0或为1的个数一定不相等，因为对于Majority Element，它的个数大于总数一半，如果它在某一bit为1，则这一bit1的个数一定大于0的个数，其为0的位同理。所以只要能找到1的个数大于0的个数的位，就能确定Majority Element。C++代码如下：
class Solution { public: int majorityElement(vector<int>& nums) { int n=nums.size(); int major=0; int i,j; int mask=1; int count; for(i=0;i<32;i++) { count=0; for(j=0;j<n;j++) { if(nums[j]&mask) { count++; if(count>n/2) { major|=mask; break; } } } mask<<=1; } return major; } } 由于外循环32次，内循环n次，所以时间复杂度O(n)。此段代码中需要注意的C++知识有如下几点： 位操作时常常会创建一个mask，用于提取目标数据的某一位，通过&、^、|等运算完成相关操作。mask<<1不会改变mask的值，必须采用mask=mask<<1，mask<<1只是产生一个两倍于mask的零时变量。
为了找到序列中最大的元素，我们自然回想如果能建立一个表，利用关键字(Key)来访问其中内容(Value)，在这一题里，关键字就是序列中元素的值，而内容就是该关键字出现的次数。遍历序列，每得到一个关键字就去表里查找，如果找不到该关键字，就插入一个，并将其内容令为1，如果查到，则将其内容加一。如果某个关键字对应Value>n/2，则说明这个关键字是Majority Element。C++中，上述功能可以用关联容器来完成，其中一种关联容器为unordered_map，这是一种采用哈希管理操作的无序容器。C++代码如下：
class Solution { public: int majorityElement(vector<int>& nums) { int n=nums.size(); unordered_map<int,int> count; int i; for(i=0;i<n;i++) { ++count[nums[i]]; if(count[nums[i]]>n/2) return nums[i]; } } }; 算法中由于关联容器的访问、修改操作基于链接法散列表，其字典操作复杂度均为O(1)，所以整个算法复杂度为O(n)。算法的重点为关联容器的使用：
unordered_map<int,int> count; 和其他容器类模板一样，实例化时需要后跟<>，里面为元素的类型，关联容器的元素为标准库pair类型，有两个共有成员，pair.first和pair.second，在本算法中，first为关键值，也就是序列中的元素，second为某一个数出现的次数。unordered_map类型和其他map类型一样，通常被称为关联数组，可以以关键字作为下标来找值，如代码中count[nums[i]]，就是用关键字nums[i]作为下标，访问其出现次数。
值得注意的是，Vector容器可以利用下标访问容器中的元素，而关联容器用关键值作为下标只能访问其关联的值，容器元素（Pair类对象）只能由迭代器访问。
无序容器在存储上组织为一组桶 T，如上图，关键字通过哈希函数映射到桶的下标，由于桶的数目小于关键字所在全域，所以不同的关键字可能映射到同一个桶，发生冲突，通常采用在桶上挂链表的方式解决冲突。这种数据结构其实是一个通过链接法解决冲突的散列表，散列表上的字典操作（插入、查找、删除）在简单均匀散列的假设（一个关键字能被等可能地散列到任何一个桶中）下复杂度为O(1)。关于关联容器的详细内容参见《C++ Primer》374页，关于Hash Table的详细内容参见《算法导论》142页，关于链表的详细内容参见《算法导论》131页。
