【优选算法】（第二十三篇）

目录

快速选择算法（medium）

题目解析

讲解算法原理

编写代码

最⼩的k个数（medium）

题目解析

讲解算法原理

编写代码

---

快速选择算法（medium）

题目解析

1.题目链接：. - 力扣（LeetCode）

2.题目描述

给定整数数组nums和整数k，请返回数组中第k个最⼤的元素。
请注意，你需要找的是数组排序后的第k个最⼤的元素，⽽不是第k个不同的元素。
你必须设计并实现时间复杂度为O(n)的算法解决此问题。
⽰例1:
输⼊:[3,2,1,5,6,4],k=2
输出:5
⽰例2:
输⼊:[3,2,3,1,2,4,5,5,6],k=4
输出:4

提⽰：
1<=k<=nums.length<=10^5
-10^4<=nums[i]<=10^4

讲解算法原理

解法（快速选择算法）：
算法思路：
在快排中，当我们把数组「分成三块」之后： [l, left] [left + 1, right - 1] [right, r] ，我们可以通过计算每⼀个区间内元素的「个数」，进⽽推断出我们要找的元素是在「哪⼀个区间」⾥⾯。
那么我们可以直接去「相应的区间」去寻找最终结果就好了。

编写代码

c++算法代码：

class Solution
{
public:int findKthLargest(vector<int>& nums, int k) {srand(time(NULL));return qsort(nums, 0, nums.size() - 1, k);}int qsort(vector<int>& nums, int l, int r, int k){if(l == r) return nums[l];// 1. 随机选择基准元素int key = getRandom(nums, l, r);// 2. 根据基准元素将数组分三块int left = l - 1, right = r + 1, i = l;while(i < right){if(nums[i] < key) swap(nums[++left], nums[i++]);else if(nums[i] == key) i++;else swap(nums[--right], nums[i]);}// 3. 分情况讨论int c = r - right + 1, b = right - left - 1;if(c >= k) return qsort(nums, right, r, k);else if(b + c >= k) return key;else return qsort(nums, l, left, k - b - c);}int getRandom(vector<int>& nums, int left, int right){return nums[rand() % (right - left + 1) + left];}
};

java算法代码：

class Solution
{public int findKthLargest(int[] nums, int k) {return qsort(nums, 0, nums.length - 1, k);}public int qsort(int[] nums, int l, int r, int k) {if(l == r) {return nums[l];}// 1. 按照随机选择的基准元素，将数组分三块int key = nums[new Random().nextInt(r - l + 1) + l];int left = l - 1, right = r + 1, i = l;while(i < right) {if(nums[i] < key) swap(nums, ++left, i++);else if(nums[i] == key) i++;else swap(nums, --right, i);}// 2. 分情况讨论int c = r - right + 1, b = right - left - 1;if(c >= k) return qsort(nums, right, r, k);else if(c + b >= k) return key;else return qsort(nums, l, left, k - b - c);}public void swap(int[] nums, int i, int j) {int t = nums[i];nums[i] = nums[j];nums[j] = t;}
}

最⼩的k个数（medium）

题目解析

1.题目链接：. - 力扣（LeetCode）

2.题目描述

输⼊整数数组arr，找出其中最⼩的k个数。例如，输⼊4、5、1、6、2、7、3、8这8个数字，则最⼩的4个数字是1、2、3、4。
⽰例1：
输⼊：arr=[3,2,1],k=2
输出：[1,2]或者[2,1]
⽰例2：
输⼊：arr=[0,1,2,1],k=1
输出：[0]

限制：
0<=k<=arr.length<=10000
0<=arr[i]<=10000

讲解算法原理

解法（快速选择算法）：
算法思路：
在快排中，当我们把数组「分成三块」之后： [l, left] [left + 1, right - 1] [right, r] ，我们可以通过计算每⼀个区间内元素的「个数」，进⽽推断出最⼩的k个数在哪些区间⾥⾯。
那么我们可以直接去「相应的区间」继续划分数组即可。

编写代码

c++算法代码：

class Solution
{
public:vector<int> getLeastNumbers(vector<int>& nums, int k) {srand(time(NULL));qsort(nums, 0, nums.size() - 1, k);return {nums.begin(), nums.begin() + k};}void qsort(vector<int>& nums, int l, int r, int k){if(l >= r) return;// 1. 随机选择⼀个基准元素 + 数组分三块int key = getRandom(nums, l, r);int left = l - 1, right = r + 1, i = l;while(i < right){if(nums[i] < key) swap(nums[++left], nums[i++]);else if(nums[i] == key) i++;else swap(nums[--right], nums[i]);}// [l, left][left + 1, right - 1] [right, r]// 2. 分情况讨论int a = left - l + 1, b = right - left - 1;if(a > k) qsort(nums, l, left, k);else if(a + b >= k) return;else qsort(nums, right, r, k - a - b);}int getRandom(vector<int>& nums, int l, int r){return nums[rand() % (r - l + 1) + l];}
};

java算法代码：

class Solution
{public int[] getLeastNumbers(int[] nums, int k) {qsort(nums, 0, nums.length - 1, k);int[] ret = new int[k];for(int i = 0; i < k; i++)ret[i] = nums[i];return ret;}public void qsort(int[] nums, int l, int r, int k){if(l >= r) return;// 1. 随机选择⼀个基准元素 + 数组分三块int key = nums[new Random().nextInt(r - l + 1) + l];int left = l - 1, right = r + 1, i = l;while(i < right){if(nums[i] < key) swap(nums, ++left, i++);else if(nums[i] == key) i++;else swap(nums, --right, i);}// 2. 分类讨论int a = left - l + 1, b = right - left - 1;if(a > k) qsort(nums, l, left, k);else if(a + b >= k) return;else qsort(nums, right, r, k - a - b);}public void swap(int[] nums, int i, int j){int t = nums[i];nums[i] = nums[j];nums[j] = t;}
}