215. 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.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

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

复杂度: 要求time O(n), space O(1)

思路: 利用快排的思想来解这道题目, 每次排序,我们要找到这样一个pivot的位置pos, 使得pos左边的都比pivot要大, pos右边的都比pivot要小。 此时如果 1. pos+1==k的话,pos位置上的元素也就是第k个元素。 2. pos+1k的话,需要往左边找,[left, pos-1]的范围

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k < 0) return -1;
        return quickSort(nums, k, 0, nums.length - 1);    
    }

    public int quickSort(int[] nums, int k, int left, int right) {
        if (left >= right) return nums[right];
        int pivot = nums[left];
        int pos = left;
        for (int i = pos + 1; i <= right; i++) {
            if (nums[i] > pivot) {
                pos++;
                swap(nums, i, pos);
            }
        }
        swap(nums, pos, left); // swap the pivot and last element
        if (pos + 1 == k) {
            return nums[pos];
        } else if (pos + 1 < k) {
            return quickSort(nums, k, pos + 1, right );
        } else {
            return quickSort(nums, k, left, pos - 1);
        }

    }

    public void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s