Title
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.
Solution
找出现次数超过n/2的数字，因此就是找第n/2大的数字嘛，因为超过n/2了，肯定是有序的中间的那个位置有这个数字呀！！！
利用快速排序O(n)找第k个数字的方法，找第n/2个，不过看leetcode的Solution的解放还是挺多的，记得一会得去看下！！
//cpp:
class Solution {
public:
int partition(vector<int> &n, int left, int right) {
int p = n[left];
while (left < right) {
while (left<right&&n[right]>p)
right--;
if (left < right) {
n[left] = n[right];
left++;
}
while (left < right&&n[left] < p)
left++;
if (left < right) {
n[right] = n[left];
right--;
}
}
n[left] = p;
return left;
}
int f(vector<int> &n, int left, int right) {
int p = partition(n, left, right);
if (p == n.size() / 2) {
return n[p];
}
else if (p < n.size() / 2) {
return f(n, p + 1, right);
}
else {
return f(n, left, p - 1);
}
}
int majorityElement(vector<int>& nums) {
return f(nums, 0, nums.size() - 1);
}
};