408算法练习——数组中第K个最大元素

本文主要是介绍408算法练习——数组中第K个最大元素，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

数组中第K个最大元素

题目链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

一、问题描述

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
 

提示：

1 <= k <= nums.length <= 104
-104 <= nums[i] <= 104

二、问题分析

　　显然这是一道排序题，而且此处是对数组操作，数组支持随机存取，就可以在排序后直接取到第k个最大元素，所以直接在原数组上实现快排即可，当然随机快排更好，可以得到更优的时间复杂度，只需要用一个随机数就可以实现，这里就不给出随机快排的算法了。

三、代码

 1 class Solution {
 2     public int findKthLargest(int[] nums, int k) {
 3         quicksort(nums,0,nums.length-1);
 4         return nums[k-1];
 5     }
 6     //快速排序递归函数
 7     public void quicksort(int[] nums,int left,int right){
 8         if(left<right){
 9             int nleft = partition(nums,left,right);
10             quicksort(nums,left,nleft-1);
11             quicksort(nums,nleft+1,right);
12         }
13     }
14     public int partition(int nums[],int left,int right){
15         int priov = nums[left];
16         int i = left;
17         for(int j=left+1;j<=right;j++){
18             if(nums[j]>=priov){
19                 i=i+1;
20                 int temp = nums[i];
21                 nums[i] = nums[j];
22                 nums[j] = temp;
23             }
24         }
25         int temp = nums[i];
26         nums[i] = nums[left];
27         nums[left] = temp;
28         return i;
29     }
30 }

　　这道题的题解中给出了更好的解决方法，因为需要的只是第k个最大元素，所以在划分过程中可以对代码进行优化（结果数组的第k个位置如果被固定就可以直接返回了）具体方法可以看官方题解

这篇关于408算法练习——数组中第K个最大元素的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！