lintcode 中等题:kth-largest-element 第k大元素

题目

第k大元素

在数组中找到第k大的元素

样例

给出数组[9,3,2,4,8],第三大的元素是4

给出数组 [1,2,3,4,5],第一大的元素是5,第二大的元素是4,第三大的元素是3,以此类推

注意

你可以交换数组中的元素的位置

挑战

要求时间复杂度为O(n),空间复杂度为O(1)

解题

理论快速排序的思想,每次都减半,这个时间复杂度也是O(N),至于为什么就不知道了

class Solution {
    /*
     * @param k : description of k
     * @param nums : array of nums
     * @return: description of return
     */
    public int kthLargestElement(int k, int[] nums) {
        // write your code here
        return quickSort(nums,0,nums.length-1,k);

    }
    public int quickSort(int[] nums,int left,int right,int k){
        int i = left;
        int j = right;
        int tmp = nums[i];
        while(i<j){
            while(i<j && tmp>=nums[j]) j--;
            if(i<j){
                nums[i]=nums[j];
                i++;
            }
            while(i<j && tmp<nums[i]) i++;
            if(i<j){
                nums[j]=nums[i];
                j--;
            }

        }
        if(i == k -1){
            return tmp;
        }else if(i< k-1){
            return quickSort(nums,i+1,right,k);
        }else{
            return quickSort(nums,left,i-1,k);
        }
    }
};

时间: 01-03

lintcode 中等题:kth-largest-element 第k大元素的相关文章

Kth Largest Element II Lintcode

Find K-th largest element in an array. and N is much larger than k. Notice You can swap elements in the array Example In array [9,3,2,4,8], the 3rd largest element is 4. In array [1,2,3,4,5], the 1st largest element is 5, 2ndlargest element is 4, 3rd

[LeetCode] Kth Largest Element in an Array 数组中第k大的数字

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'

Java for LeetCode 215 Kth Largest Element in an Array【Coming Soon】

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. 解题思路: 本题是<算法导论>原题,

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 le

leetcode Kth Largest Element in an Array

题目连接 https://leetcode.com/problems/kth-largest-element-in-an-array/ Kth Largest Element in an Array Description 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 eleme

LeetCode 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

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'

LeetCode215: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'

【leetcode】Kth Largest Element in an Array (middle)☆

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. 思路: 堆.讲解:二叉堆 class Solution { public: //新插入i结点 其父节点为(i