怎么制作网站生成图片,土巴兔网站开发方案,规范12388举报网站建设管理,手机版自适应网站怎么做目录 快速选择算法#xff08;medium#xff09;
题目解析
讲解算法原理
编写代码
最⼩的k个数#xff08;medium#xff09;
题目解析
讲解算法原理
编写代码 快速选择算法#xff08;medium#xff09;
题目解析
1.题目链接#xff1a;. - 力扣#xff08;L…目录 快速选择算法medium
题目解析
讲解算法原理
编写代码
最⼩的k个数medium
题目解析
讲解算法原理
编写代码 快速选择算法medium
题目解析
1.题目链接. - 力扣LeetCode
2.题目描述 给定整数数组nums和整数k请返回数组中第k个最⼤的元素。 请注意你需要找的是数组排序后的第k个最⼤的元素⽽不是第k个不同的元素。 你必须设计并实现时间复杂度为O(n)的算法解决此问题。 ⽰例1: 输⼊:[3,2,1,5,6,4],k2 输出:5 ⽰例2: 输⼊:[3,2,3,1,2,4,5,5,6],k4 输出:4 提⽰ 1knums.length10^5 -10^4nums[i]10^4 讲解算法原理
解法快速选择算法 算法思路 在快排中当我们把数组「分成三块」之后 [l, left] [left 1, right - 1] [right, r] 我们可以通过计算每⼀个区间内元素的「个数」进⽽推断出我们要找的元素是在「哪⼀个区间」⾥⾯。 那么我们可以直接去「相应的区间」去寻找最终结果就好了。
编写代码
c算法代码
class Solution
{
public:int findKthLargest(vectorint nums, int k) {srand(time(NULL));return qsort(nums, 0, nums.size() - 1, k);}int qsort(vectorint 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(vectorint 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],k2 输出[1,2]或者[2,1] ⽰例2 输⼊arr[0,1,2,1],k1 输出[0] 限制 0karr.length10000 0arr[i]10000 讲解算法原理
解法快速选择算法 算法思路 在快排中当我们把数组「分成三块」之后 [l, left] [left 1, right - 1] [right, r] 我们可以通过计算每⼀个区间内元素的「个数」进⽽推断出最⼩的k个数在哪些区间⾥⾯。 那么我们可以直接去「相应的区间」继续划分数组即可。
编写代码
c算法代码
class Solution
{
public:vectorint getLeastNumbers(vectorint nums, int k) {srand(time(NULL));qsort(nums, 0, nums.size() - 1, k);return {nums.begin(), nums.begin() k};}void qsort(vectorint 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(vectorint 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;}
}
