215. 数组中的第K个最大元素

电玩女神 2023-02-08 12:48 11阅读 0赞

链接：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

## 题目分析 ##

这道题，实际上就是考排序算法。对数组从大到小排序完，返回 nums\[k-1\] 。  
排序方法有很多，就像那十大排序法。

官方题解提供了快速排序和堆排序两种方案，时间和空间复杂度各有优势：

<table> 
 <thead> 
  <tr> 
   <th>排序算法</th> 
   <th>时间复杂度</th> 
   <th>空间复杂度</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>快速排序</td> 
   <td>O(n)</td> 
   <td>O(logn)</td> 
  </tr> 
  <tr> 
   <td>堆排序</td> 
   <td>O(nlogn)</td> 
   <td>O(logn)</td> 
  </tr> 
 </tbody> 
</table>

我这里使用了选择排序。它有个特点是，  
经过第1次遍历，第1大的元素就在 nums\[0\]；  
经过第2次遍历，第2大的元素就在 nums\[1\]；  
…  
经过第k次遍历，第k大的元素在 nums\[k-1\]

## 代码实现 ##

class Solution {
        
        public int findKthLargest(int[] nums, int k) {
        
            for (int i = 0; i < nums.length; i++) {
        
                int maxIndex = i;
                for (int j = i + 1; j < nums.length; j++) {
        
                    if (nums[j] > nums[maxIndex]) {
        
                        maxIndex = j; // 找到最大元素的下标
                    }
                }
                // 交换元素
                int tmp = nums[i];
                nums[i] = nums[maxIndex];
                nums[maxIndex] = tmp;
    
                // 第i次结束，实际上第 i+1 大的元素就出来了，后面的就不排了
                if (i + 1 == k) {
        
                    break;
                }
            }
            return nums[k-1];
        }
    }

时间复杂度：最坏情况当 k 等于 n 时，为 O(n^2)。k = 1时，O(n)  
空间复杂度：因为没申请额外数组，O(1)  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAa2tra2s3MjEw_size_20_color_FFFFFF_t_70_g_se_x_16]

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAa2tra2s3MjEw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20230208/8c1463eca13c408e9ffc5da45f51201c.png