Alibi

My Life is Getting Better

Leetcode[211]Kth Largest Element in an Array

19 Nov 2015

###Task1 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.

###Python ####O(n)

class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        if not nums or len(nums) < k:
            return -1
        return self.qs(nums, len(nums) - k, 0, len(nums) - 1)
    
    def qs(self, nums, k, start, end):
        pivot = nums[end]
        left = start
        right = end
        while True:
            while left < right and nums[left] < pivot:
                left += 1
            while left < right and nums[right] >= pivot:
                right -= 1
            if left == right:
                break
            nums[left], nums[right] = nums[right], nums[left]
        nums[left], nums[end] = nums[end], nums[left]
        if k == left:
            return nums[right]
        elif k < left:
            return self.qs(nums, k, start, left - 1)
        else:
            return self.qs(nums, k, left + 1, end)

###Java

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        
        return quick(nums, 0, nums.length - 1, nums.length - k);
    }
    
    public void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
    
    public int quick(int[] nums, int start, int end, int k) {
        int left = start;
        int right = end;
        while (true) {
            while (left < right && nums[left] < nums[end]) {
                left++;
            }
            while (left < right && nums[right] >= nums[end]) {
                right--;
            }
            if (left == right) {
                break;
            }
            swap(nums, left, right);
        }
        swap(nums, left, end);
        
        if (left == k) {
            return nums[left];
        } else if (left > k) {
            return quick(nums, start, left - 1, k);
        } else {
            return quick(nums, left + 1, end, k);
        }
    }
}

###Points

Related Posts