215. Kth Largest Element in an Array

栏目: Java · 发布时间: 4年前

内容简介: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.Example 1:Example 2:

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.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note:

You may assume k is always valid, 1 ≤ k ≤ array's length.

难度:medium

题目:找出在没有 排序 的数组中第K大的元素,注意是排序后的第K大的元素,不是第K个不同元素。

思路:快速排序

Runtime: 29 ms, faster than 36.08% of Java online submissions for Kth Largest Element in an Array.

Memory Usage: 38.8 MB, less than 51.09% of Java online submissions for Kth Largest Element in an Array.

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int idx = -1;
        k = nums.length - k;
        for (int i = 0, j = nums.length - 1; i <= j && idx != k;) {
            idx = quickSort(nums, i, j);
            if (idx < k) {
                i = idx + 1;
            } else if (idx > k) {
                j = idx - 1;
            }
        }
        
        return nums[idx];
    }
    
    private int quickSort(int[] nums, int i, int j) {
        int piovt = nums[i];
        while (i < j) {
            while (i < j && nums[j] >= piovt) {
                j--;
            }
            nums[i] = nums[j];
            while (i < j && nums[i] < piovt) {
                i++;
            }
            nums[j] = nums[i];
        }
        nums[i] = piovt;
        
        return i;
    }
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

增长的本质

增长的本质

凯萨·伊达尔戈 / 中信出版集团股份有限公司 / 2015-11-1 / CNY 49.00

这是一本物理学家撰写得跨经济学、社会、物理学等多学科的专著。在伊达尔戈之前,从来没有人以这样的方式研究经济增长。 什么是经济增长?为什么它只发生在历史长河的一些节点上?传统意义上的解释都强调了体制、地理、金融和心理因素。而塞萨尔?伊达尔戈告诉我们,想了解经济增长的本质,还需要走出社会科学的研究,在信息、关系网和复杂性这样的自然科学中寻求答案。为了认识经济发展,塞萨尔?伊达尔戈认为我们首先需要......一起来看看 《增长的本质》 这本书的介绍吧!

在线进制转换器
在线进制转换器

各进制数互转换器

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具

html转js在线工具
html转js在线工具

html转js在线工具