求众数

给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在众数。

示例 1:

输入: [3,2,3]
输出: 3

示例 2:

输入: [2,2,1,1,1,2,2]
输出: 2

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/majority-element
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    //因为出现次数大于n/2,所以排序后中间值一定是众数
    public int majorityElement(int[] nums) {
        // sort(nums);
        sort(nums,0,nums.length-1);
        //Arrays.sort(nums);//数组自带的有排序，呵呵
        return nums[nums.length / 2];
    }
    
    private void sort(int[] nums,int _left,int _right){
        //快排
        int left = _left;
        int right = _right;
        int temp;
        if(left <= right){
            temp = nums[left];
            while(left != right){
                while(left < right && nums[right] >= temp){
                    right--;
                }

                nums[left] = nums[right];

                while(left < right && nums[left] <= temp){
                    left++;
                }
                
                nums[right] = nums[left];
            }
            
            nums[left] = temp;
            sort(nums, _left, left - 1);
            sort(nums, right + 1, _right);
        }
    }
}