39-数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

三种思路：1.直接排序 2.使用Map 3.使用partition()

class Solution {
    private int[] nums;
    public int majorityElement(int[] nums) {
        if (nums.length <= 2) return nums[0];
        this.nums = nums;
        int i = 0, j = nums.length - 1;
        int mid = j / 2;
        while(i < j) {
            int index = partition(i, j);
            if (index == mid) {
                return nums[index];
            } else if (index < mid) {
                i = index + 1;
            } else if (index > mid) {
                j = index - 1;
            }
        }
        return nums[mid];
    }

    private int partition(int lo, int hi) {
        int i = lo, j = hi + 1;
        int c = nums[lo];
        while(i < j) {
            while(nums[++i] < c && i < hi);
            while(nums[--j] > c && j > lo);
            if (i < j) swap(i, j);
        }
        // 跳出循环时 i >= j, j 是较小的索引
        swap(lo, j);
        return j;
    }

    private void swap(int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}