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

ゞ浴缸里的玫瑰 2022-11-21 15:08 113阅读 0赞

**题意：**

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

**思路：**

> 利用快排来完成这个操作，对于某次快排操作后我们可以得到一个下标p，小于p的都位于p的左边，大于p的都位于p的右边。如果p==k，说明正好是我们要寻找的数，返回即可。如果p<k，那么我们就再对右数组进行快排操作。

**代码：**

class Solution { 
    public:
    
    	int slove(vector<int>& nums, int L, int R)
    	{ 
            swap(nums[L], nums[L + rand() % (R - L + 1)]); //随机，避免最坏情况
    		int val = nums[L];
    		while(L < R)
    		{ 
    			while(L < R && nums[R] >= val) --R;
    			swap(nums[L], nums[R]);
    			while(L < R && nums[L] <= val) ++L;
    			swap(nums[L], nums[R]);
    		}
    		return L;
    	}
    	int quicksort(vector<int>& nums, int L, int R, int k)
    	{ 
    		int pos = slove(nums, L, R);
    		if(pos == k) return nums[pos];
    		if(L < R)
    		{ 
    			if(pos < k) return quicksort(nums, pos + 1, R, k);
    			return quicksort(nums, L, pos - 1, k);
    		}
    		return -1;
    	}
    
    	int findKthLargest(vector<int>& nums, int k) { 
            srand(time(0));
    		if(nums.size() == 1) return nums[0];
    		return quicksort(nums, 0, nums.size() - 1, nums.size() - k);
    	}
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，113人围观）

还没有评论，来说两句吧...

相关阅读

相关【LeetCode 215】数组中的第K个最大元素

题目描述在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。示例 1: 输入: [

梦里梦外;/ 2022年12月04日 07:53/ 0 赞/ 156 阅读

相关【堆】 LeetCode215. 数组中的第K个最大元素

题目 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmN

港控/mmm°/ 2022年12月03日 09:20/ 0 赞/ 163 阅读

相关 LeetCode215. 数组中的第K个最大元素

题意： > 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。思路： > 利用快排来完成这个操

ゞ浴缸里的玫瑰/ 2022年11月21日 15:08/ 0 赞/ 114 阅读

相关 leetcode#215.数组中的第K个最大元素

出处 https://leetcode-cn.com/problems/kth-largest-element-in-an-array/ 题目在未排序的数组中找

r囧r小猫/ 2022年11月04日 11:13/ 0 赞/ 154 阅读

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

r囧r小猫/ 2022年10月28日 10:10/ 0 赞/ 139 阅读

相关 LeetCode215. 数组中的第K个最大元素

难度：中等题目描述： > 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。示例 1:

系统管理员/ 2022年10月20日 05:26/ 0 赞/ 151 阅读

相关 Leetcode215 数组中的第K个最大元素

题目描述在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。示例 1: 输入: \[3

小咪咪/ 2022年10月16日 14:21/ 0 赞/ 149 阅读

相关 Leetcode215-数组中的第K个最大元素

数组中的第K个最大元素给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个

爱被打了一巴掌/ 2022年09月03日 10:27/ 0 赞/ 128 阅读

相关【LeetCode】215. 数组中的第K个最大元素

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

阳光穿透心脏的1/2处/ 2022年05月08日 06:54/ 0 赞/ 179 阅读

相关 leetcode:215. 数组中的第K个最大元素

题目: 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。示例 1: 输入: \[3,2,

小灰灰/ 2022年03月09日 01:27/ 0 赞/ 183 阅读