题目描述：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。

解题思路：
1、哈希表。统计每一个数字出现的次数，若出现比数组长度一半还大的出现次数，则直接返回该数。
2、排序，返回中位数。比数组长度一半还大的数经过排序后，中位数一定是该数。可以利用快排，确定中位数即可返回。
C++（本题超时，卡在最后一组用例）

class Solution {
public:
    bool flag;
    int t_index;
    int majorityElement(vector<int>& nums) {
        int size = nums.size();
        t_index = size / 2;
        flag = false;
        quickSort(nums, 0, size - 1, t_index);
        return nums[t_index];
    }
    int findPartition(vector<int>& v, int left, int right){
        int base = v[left];
        int i = left;
        int j = right;
        while(i < j){
            while(i < j && v[j] >= base) j--;
            v[i] = v[j];
            while(i < j && v[i] <= base) i++;
            v[j] = v[i];
        }
        v[i] = base;
        return i;
    }
    void quickSort(vector<int>& v, int left, int right, int t_index){
        if(left >= right) return;
        int index = findPartition(v, left, right);
        if(index == t_index){
            flag = true;
            return;
        }
        quickSort(v, left, index - 1, t_index);
        if(flag) return;
        quickSort(v, index + 1, right, t_index);
    }
};

Java同理
⭐3、摩尔投票法。
假设所求数为x，nums数组总数为n，设置一个投票总数votes，初始化为0。
当num == x时，votes += 1;
当num != x时，votes -=1;
基本原理：假设数组首个元素a为所求数（x = a;），遍历并统计票数。当发生 votes == 0 时，x一定仍存在于剩余数组中，我们可以不断的缩小x的范围(x = num)，直到最后x即为所求数。
这是因为：
(1) 若a == x，即a就是次数超过数组一半的数。可以确定已经遍历的数字中 x 与 !x 出现的次数一样，而x因为次数超过数组一半，所以剩余数组中一定仍存在x。
(2) 若a != x，即a不是我们所求数。说明已经遍历的数字中 size(a) == size(!x) - size(a) + size(x)，而x因为次数超过数组的一般，所以剩余数组中一定仍存在x。
C++

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int votes = 0;
        int x;
        for(int i = 0; i < nums.size(); i++){
            if(votes == 0) x = nums[i];
            votes += x == nums[i] ? 1 : -1;
        }
        return x;
    }
};

Java同理

对于数组[1, 2, 1, 2, 3]
（1）该数组中的众数有1，2。题目中的次数超过数组长度的一半的数字不等于众数。寻找众数时摩尔投票法失效。
（2）题目中特意说明了，该数一定存在。若可能不存在（例如上述数组），则要校验最后的x的出现次数是否超过了数组长度的一半。即要重新遍历数组，计算出现的次数。