当前位置:   article > 正文

数组中第 K 大的数(leetcode 215)_给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。

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

1.问题描述

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

示例 1:

输入: [3,2,1], k = 1
输出: 3
  • 1
  • 2

示例 2:

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

示例 3:

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

2.难度等级

medium。

3.热门指数

★★★★★

出题公司:腾讯、B站

4.解题思路

基于快速排序的二分可以做到 O(n) 的时间复杂度。

先回顾一下快速排序,其属交换类排序,采用分治的思想,完成对无序数列的排序。

其核心操作是从数组中选择任意一个元素(通常选取第一个)作为分界值,通过双指针遍历数组,采用交换的方式使得左边的元素都小于等于它,右边的元素都大于等于它。

从快排的核心操作中可以看到,如果分界值的位置刚好是 K(升序为从后往前数),那么该分界值为数组中第 K 大的数。如果分界值的位置小于 K,则继续在右子数组中按照相同的方式寻找,反之在左子数组中寻找。循环往复,直至找到第 K 大的数。

复杂度分析:

时间复杂度:平均 O(n)。假设数组是无序的,每一次划分将数组一分为二。第一次划分时间复杂度是 O(n),第二次划分是 O(n/2)。最差的情况,最后一次即 logn 次找到第 K 大的数,那么时间复杂度为 n + n/2 + n/4 + … + 1 = O(n)。

空间复杂度:O(1)。没有借助辅助空间来存放数组。

5.实现示例

5.1 C++

// findKthLargest 寻找数组中第 K 大的数。
int findKthLargest(vector<int> &nums, int k) {
  int l = 0, r = nums.size() - 1;
  while (true) {
    int pivot = nums[l];
    int i = l, j = r;
    while (i != j) {
      while (nums[j] >= pivot && j > i) {
        j--;
      }
      while (nums[i] <= pivot && i < j) {
        i++;
      }
      int tmp = nums[i];
      nums[i] = nums[j];
      nums[j] = tmp;
    }
    int tmp = nums[l];
    nums[l] = nums[i];
    nums[i] = tmp;

    // 找到第 K 大的数。
    if (nums.size() - i == k) {
      return nums[i];
    }
    // 第 K 大的数在右区间。
    if (nums.size() - i > k) {
      l = i + 1;
      continue;
    }
    // 第 K 大的数在左区间。
    if (nums.size() - i < k) {
      r = i - 1;
      continue;
    }
  }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37

验证代码:

#include <iostream>
#include <vector>
using namespace std;

int main() {
  auto vec = vector<int>{3,2,1};
  cout << findKthLargest(vec, 1) << endl;
  vec = vector<int>{3,2,1,5,6,4};
  cout << findKthLargest(vec, 2) << endl;
  vec = vector<int>{3,2,3,1,2,4,5,5,6};
  cout << findKthLargest(vec, 4) << endl;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

运行输出:

3
5
4
  • 1
  • 2
  • 3

5.2 Golang

// findKthLargest 寻找数组中第 K 大的数。
func findKthLargest(nums []int, k int) int {
    l, r := 0, len(nums)-1
  	for {
		pivot := nums[l]
		i, j := l, r
		for i != j {
			for nums[j] >= pivot && j > i {
				j--
			}
			for nums[i] <= pivot && i < j {
				i++
			}
			nums[i], nums[j] = nums[j], nums[i]
		}
		nums[l], nums[i] = nums[i], nums[l]
	  	// 找到第 K 大的数。
		if len(nums) - i == k {
			return nums[i]
		}
        // 第 K 大的数在右区间。
		if len(nums) - i > k {
			l = i + 1
			continue
		}
        // 第 K 大的数在左区间。
		if len(nums) - i < k {
			r = i - 1
			continue
		}
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32

验证代码:

package main

import (
	"fmt"
)

func main() {
  fmt.Println(findKthLargest([]int{3,2,1}, 1))
  fmt.Println(findKthLargest([]int{3,2,1,5,6,4}, 2))
  fmt.Println(findKthLargest([]int{3,2,3,1,2,4,5,5,6}, 4))
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

运行输出:

3
5
4
  • 1
  • 2
  • 3

参考文献

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

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/你好赵伟/article/detail/206281
推荐阅读
相关标签
  

闽ICP备14008679号