LeetCode(Sort&Search)Kth Largest Element in an Array

Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

思路：没什么好说的，最简单最直接的方法就是排序，然后返回第k大的数。写了一个插入排序，java代码如下。

class Solution {
    public int findKthLargest(int[] nums, int k) {
        insertSort(nums);
        return nums[nums.length-k];
    }
    
    private void insertSort(int [] arr){
        for(int i=1;i<arr.length;i++){
            int temp=arr[i];
            int j;
            for(j=i-1; j>=0 && temp<arr[j]; j--){
                arr[j+1]=arr[j];
            }
            arr[j+1]=temp;
        }
    }
}