题解 | #草原上优势牛种#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    int[] numbers;  //将局部变量提到全局
    public int majority_cow (int[] nums) {
        // write code here
        numbers = nums;
        sort();

        //因为出现次数最多的数总是大于数组长度的一半，所以直接返回数组中间的值
        return nums[nums.length / 2];
    }

    /**
     * 快速排序
    *     先取start索引位置为基准值，left指针一直向右找是否存在比基准值大的数字，right指针向
     * 左找比基准值小的数，然后交换，right指针指向的就是交换后基准值所在的位置,然后再对基准值
     * 左右分别排序
     */
    public void sort(){
        int start = 0 , end = numbers.length - 1;
        sort(start , end);
    }

    public void sort(int start , int end){
        if(start >= end)
            return;
        int part = part(start, end);
        sort(start , part - 1);
        sort(part + 1 , end);
    }

    public int part(int start , int end){
        int left = start , right = end + 1;
        int n = numbers[start];
        while(true){
            while(numbers[++left] <= n){
                if(left == end)
                    break;

            }

            while(numbers[--right] > n){
                if(right == start)
                    break;
            }

            if(left >= right)
                break;

            int temp = numbers[left];
            numbers[left] = numbers[right];
            numbers[right] = temp;
        }

        int temp = numbers[start];
        numbers[start] = numbers[right];
        numbers[right] = temp;

        return right;
    }
}