lintcode 5 · Kth Largest Element

本文主要是介绍lintcode 5 · Kth Largest Element，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

https://www.lintcode.com/problem/5/?_from=cat

[]
what is the bug?

[code]

public class Solution {
    /**
     * @param k: An integer
     * @param nums: An array
     * @return: the Kth largest element
     */
    public int kthLargestElement(int k, int[] nums) {
        // write your code here

        return kthLargestElement(k, nums, 0, nums.length-1);
    }

    int kthLargestElement(int k, int[] nums, int l, int r){
        
        int pInx = partition(nums, l, r);
        int len = nums.length;
        if(pInx > len - k){
            int rlen = len-1 - pInx;
            return kthLargestElement(k-rlen-1, nums, l, pInx-1);
        }
        if(pInx < len - k){
            return kthLargestElement(k, nums, pInx+1, r);
        }
        return nums[pInx];
    }

    int partition(int[] nums, int left, int right){
        
        int pivot = nums[left];
        int l = left + 1;
        int r = right;

        while(l < r){
            if(nums[l] < pivot){
                l++;
                continue;
            }
            if(nums[r] >= pivot){
                r--;
                continue;
            }
            swap(nums, l, r);
            l++;
            r--;
        }
        if(nums[l]>=pivot){
            l--;
        }
        swap(nums, left, l);
        return l;
    }

    void swap(int[] arr, int i, int j){
        
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

这篇关于lintcode 5 · Kth Largest Element的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！