//6.分治Time(Nlog(N)) Space:O(logN)
    public int moreThanHalfNum_Solution(int[] nums) {
        int result = divide(nums, 0, nums.length - 1);
        return checkMoreThanHalfNum(nums, result)? result : -1;
    }
    private int divide(int[] nums, int st, int ed) {
        if(st == ed) {
            return nums[st];
        }else {
            int mid = (st + ed) >> 1;
            int leftMajority = divide(nums, st, mid);
            int rightMajority = divide(nums, mid + 1, ed);
            int countLeftMajority = countMajority(nums, st, mid, leftMajority);
            int countRightMajority = countMajority(nums, mid + 1, ed, rightMajority);
            return countLeftMajority > countRightMajority?  leftMajority : rightMajority;
        }

    }
    private int countMajority(int[] nums, int st, int ed, int num) {
        int count = 0;
        for(int i = st; i <= ed; i++) {
            if(num == nums[i]) {
                ++count;
            }
        }
        return count;
    }

    //5.Integer 32bit，对每个位进行统计，如果超过nums.lenght / 2的时候，加入ans中
    //Time:O(32*N) Space:O(1)
    public int moreThanHalfNum_Solution5(int[] nums) {
        if(nums == null || nums.length == 0) return -1;
        int index = 1;
        int countBitOne = 0;
        int len = nums.length / 2;
        int ans=  0;
        for(int i = 0; i < 32; i++) {
            index = 1<<i;
            countBitOne = 0;
            for(int num : nums) {
                if((num & index) != 0) ++countBitOne;
            }
            if(countBitOne > len) {
                ans |= index;
            }
        }
        return checkMoreThanHalfNum(nums, ans)? ans : -1;
    }

    //4.摩尔投票 Time:O(n)
    public int moreThanHalfNum_Solution4(int[] nums) {
        int count = 0 , res = 0;
        for(int num : nums) {
            if(count == 0) {
                res = num;
                ++count;
            }else {
                if(res == num) {
                    ++count;
                }else {
                    --count;
                }
            }
        }
        return res;
    }
    //3.partition找中位数
    public int moreThanHalfNum_Solution3(int[] nums) {
        if(nums == null || nums.length == 0) return -1;
        int target = partition(nums, 0, nums.length - 1);
        return checkMoreThanHalfNum(nums, target)? target : -1;
    }
    private int partition(int[] nums, int st, int ed) {
        int povit = nums[st];
        int left = st, right =ed;
        while(left < right) {
            while(left < right && nums[left] <= povit) ++left;
            while(left < right && nums[right] >= povit) --right;
            if(left < right) {
                swap(nums, left, right);
                ++left;
                --right;
            }
        }
        if(left == nums.length/ 2) {
            return nums[left];
        }
        else if(left < nums.length /2) {
            return partition(nums, left+1, ed);   
        }else {
            return partition(nums, st, left-1);
        }
    }
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    //2.sort 中位数 Time:O(NlogN) space：O(1)
    public int moreThanHalfNum_Solution2(int[] nums) {
        if(nums == null || nums.length == 0) return -1;
        Arrays.sort(nums);
        int ans = nums[nums.length / 2];
        return checkMoreThanHalfNum(nums, ans)? ans : - 1;
    }

    private boolean checkMoreThanHalfNum(int[] nums, int num){
        int count = 0;
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] == num) ++count;
        }
        return count>nums.length / 2? true : false;
    }

    //1.map统计 time:O(N) Space:O(N)
    public int moreThanHalfNum_Solution1(int[] nums) {
        if(nums == null || nums.length == 0) return -1;
        Map<Integer, Integer> map = new HashMap<>();//<int, count>
        for(int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        int len = nums.length / 2;
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            if(entry.getValue() > len) 
                return entry.getKey();
        }
        return -1;
    }