AC Log - 快速选择
type: channel
link: https://aclog.neix.in/index.php/tag/%E5%BF%AB%E9%80%9F%E9%80%89%E6%8B%A9/
items: 数组中的第K个最大元素

数组中的第K个最大元素
type: item
date: 2025-12-25T06:12:20+00:00
description: 题目链接：数组中的第K个最大元素给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。方法一：快速选择class Solution { public: int quickSelect(vector<int>& nums,int k) { int pivot = nums[rand() % nums.size()]; vector<int> big,equal,small; for (int num : nums) { if (num > pivot) { big.push_back(num); }else if (num < pivot) { small.push_back(num); }else { equal.push_back(num); } } if (k <= big.size()) { return quickSelect(big,k); } if (nums.size() - small.size() < k) { return quickSelect(small,k - nums.size() + small.size()); } return pivot; } int findKthLargest(vector<int>& nums, int k) { return quickSelect(nums,k); } };