---
title: "Kth Largest Element in an Array"
author: "KickCode"
date: "2015-12-23T10:33:27Z"
tags: []
categories: ["编程语言"]
slug: "kth-largest-element-in-an-array"
draft: false
lastmod: "2016-02-21T01:53:47Z"
id: 2265890
url: "https://kickcode.iteye.com/blog/2265890"
---

**Kth Largest Element in an Array**
给定一个无序的数组，找出第K大的元素，假定k一直有效，1 ≤ k ≤ array's length。
例如给定：nuts =  ,  k = 2
返回 5

如果我们用Arrays的sort方法将数组排序，然后输出nums就是第k大的元素。代码如下：

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

```


如果我们在面试中遇到这个问题，这显然不是面试者想考察的地方。我们可以用快排是解决这个问题，在数组中取一个元素作为pivot，第一次循环后，查看pivot的位置，通过它的位置来递归找到第k大的元素。代码如下：

```java

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        return quickSort(0, nums.length - 1, nums, k);
    }
    
    public int quickSort(int l, int r, int[] nums, int k) {
        int i = l, j = r, pivot = nums[l];
        while(i < j) {
            while(i < j && nums[j] >= pivot) 
                j --;
            if(i < j) 
                nums[i++] = nums[j];
            
            while(i < j && nums[i] <= pivot)
                i ++;
            if(i < j)
                nums[j--] = nums[i];
        }
        nums[i] = pivot;
        if(nums.length - i == k) return nums[i];
        if(nums.length - i < k) return quickSort(l, i - 1, nums, k);
        return quickSort(i + 1, r, nums, k);
    }
}

```