赞
踩
给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。
示例 1:
输入: [3,2,1], k = 1
输出: 3
示例 2:
输入: [3,2,1,5,6,4], k = 2
输出: 5
示例 3:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
medium。
★★★★★
出题公司:腾讯、B站。
基于快速排序的二分可以做到 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)。没有借助辅助空间来存放数组。
// 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; } } }
验证代码:
#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;
}
运行输出:
3
5
4
// 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 } } }
验证代码:
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))
}
运行输出:
3
5
4
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。