题解 | #数组中出现次数超过一半的数字#

import java.util.*;
public class Solution {
    public static int num;
    public int MoreThanHalfNum_Solution(int [] array) {
        qsort(array, 0, array.length - 1);
        return num;
    }
    public void qsort(int []a, int l, int r) {
        // Arrays.sort(array);
        // return array[array.length/2];

        int mid = a[l];
        int left = l;
        int right = r;
        int temp = 0;
        Boolean flag = false;
        while (left < right) {
            //将和mid相等的数不断往中间和后面移动，比mid小的数不断前移
            while ( a[left] < mid &&
                    left < right) { 
                left++;
            }
            temp = a[left];
            while (a[right] > mid && left < right) { //将和mid相等的数不断往中间和前面移动，比mid大的数不断后移
                right--;

            }
            if(left!=right){//不等则a[left] >= mid && a[right] <= mid
            a[left] = a[right];
            a[right] = temp;
            left++;
            right--;
            }
            //  if(left==right)不需要替换成mid，已经是mid
            }
        if (left >= a.length / 2) {
            num = a[a.length / 2];
            return ;
        } else if (left < a.length / 2) {
            if(left==right){
            qsort(a, left + 1, r);
            }else{
            qsort(a, left, r);
            }
        }
        }

    }