数组中第k大的元素

两种思想：

1.首先是直接排序，调用sort方法实现

• java

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length-k];
    }
}

• javascript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
     nums.sort(sortNumber);
        return nums[nums.length-k];
};

function sortNumber(a,b){
    return a-b;
}

2.利用快速排序法的思想实现

• 回顾快速排序法

private void quicksort(int[] list,int start,int end) {
        //记住必须end>start
        if(end>=start){
            int piord=list[start];
            int low=start+1;
            int high=end;
            while(low<high){
                //找到左边第一个比piord大的数
                while(low<=high&&list[low]<piord)
                    low++;
                while(low<=high&&list[high]>piord)
                    high--;
                if(low<high)
                    swap(list,low,high);

            }
            //执行完循环后，找到第一个小于piord的数，和第一个数交换位置
            while(high>start&&list[high]>=piord)
                high--;
            if(list[high]<piord)
                swap(list,start,high);
            //左半边快排
            quicksort(list,start,high-1);
            //右半边快排
            quicksort(list,high+1,end);
        }

    }

    private void swap(int[] list, int i, int j) {
        int temp=list[i];
        list[i]=list[j];
        list[j]=temp;
    }

思想：重点是快速排序算法一次定一个位置，如果定下的位置就是n-k（从小到大排，n-k的位置就是第k大的位置），直接返回n-k的内容，如果定下的位置<n-k,就要在右边进行快排，如果定下的位置>n-k，就要在左边进行快排。

• java实现

class Solution {
    public int findKthLargest(int[] nums, int k) {
       return findKthLargest(nums,0,nums.length-1,k);   
    }
    
    public int findKthLargest(int[] nums,int start,int end,int k){
        if(start<=end){
            int pivot=nums[start];
            int low=start+1;
            int high=end;
            while(low<high){
                 //找到第一个大于pivot的索引
                //注意这里必须要有等于号，因为在所有数字都相等时，只要让low和high指向末尾元素即可。
                while(low<=high&&nums[low]<=pivot)
                    low++;
                //找到第一个小于pivot的索引
                while(low<=high&&nums[high]>pivot)
                    high--;
                if(low<high)
                   swap(nums,low,high);
            }
            
            while(start<high&&nums[high]>=pivot)
                high--;
            if(nums[high]<pivot)
                swap(nums,start,high);
            
            if(high==nums.length-k)
                return nums[high];
            else if(high<nums.length-k)
                //如果定出来的位置小于nums.length-k，就在右半边快排
                return findKthLargest(nums,high+1,end,k);
                //如果定出来的位置大于nums.length-k,就在左半边快排
            else
                return findKthLargest(nums,start,high-1,k);
           
        }
        
        return Integer.MAX_VALUE;
    }
    
    public void swap(int[] nums,int low,int high){
        int temp=nums[low];
        nums[low]=nums[high];
        nums[high]=temp;
    }
}

• javascript实现

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
    return findK(nums,0,nums.length-1,k);
};

var findK=function(nums,start,end,k){
    //注意，必须有等号，应对只有一个元素的情况
    if(start<=end){
        var pivot=nums[start];
        var low=start+1;
        var high=end;
        while(low<high){
            //注意必须有等号，应对所有元素均相等的情况，让low指向最后一个元素
            while(low<=high&&nums[low]<=pivot)
                low++;
            //让high也指向最后一个元素
            while(low<=high&&nums[high]>pivot)
                high--;
            if(low<high)
                swap(nums,low,high);
        }
        //找到小于pivot的第一个元素
        while(high>start&&nums[high]>=pivot)
            high--;
        if(nums[high]<pivot)
            swap(nums,start,high);
        if(high==nums.length-k)
            return nums[high];
        else if(high<nums.length-k)
            return findK(nums,high+1,end,k);
        else
            return findK(nums,start,high-1,k);
    }
}

var swap=function(nums,low,high){
    var temp=nums[low];
    nums[low]=nums[high];
    nums[high]=temp;
}