有心学做网站,青岛公司网站建设公司排名,手机上的网页游戏,想创建一个网站力扣75.颜色分类
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums #xff0c;原地对它们进行排序#xff0c;使得相同颜色的元素相邻#xff0c;并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sor…力扣75.颜色分类
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums 原地对它们进行排序使得相同颜色的元素相邻并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。 class Solution { //时间复杂度为O(n)//其实变量 zero 相当于我们在三路快速排序算法中的 lt//变量 two 相当于我们在三路快速排序算法中的 gt。public void sortColors(int[] nums) {// nums[0...zero] 0, nums[zero 1, i] 1, nums[two, n - 1] 2// 定义三个指针zero、i、two分别表示0的最右边界、当前处理的元素、2的最左边界int zero -1, i 0, two nums.length;while(i two){// 当前处理元素的指针小于2的最左边界时继续循环// 如果当前元素为0将其与zero右边的元素交换并将zero和i都向右移动一位if(nums[i] 0){zero;swap(nums,zero,i);i;}// 如果当前元素为2将其与two左边的元素交换并将two向左移动一位else if (nums[i] 2){ // 注意此时不需要i右移因为交换后的元素还需要继续判断two --;swap(nums, i, two);}else{ //如果当前元素是1不需要操作直接继续向右遍历i ;}}}// 交换数组中指定位置的两个元素private void swap(int[] nums, int i, int j){int t nums[i];nums[i] nums[j];nums[j] t;}
} 我们首先来封装一个 selectK 的方法。封装好了这个方法以后这三个问题都可 以快速求解。 我们的 selectK 的接口是这样的 // 在 arr[l...r] 的范围里求解整个数组的第 k 小元素并返回 // k 是索引即从 0 开始计算 int selectK(int[] arr, int l, int r, int k, Random rnd) 因为我们的 partition 过程需要随机选取标定点所以我们还需要传一个 Random快排的优化 类的对象 rnd。 定义好函数签名以后下面我们来书写相应的逻辑。 首先selectK 的过程我们就是要执行一遍 partition。在这里我使用双路快速 排序的 partition。 注意因为在这个问题中我们肯定我们处理的数据类型是 int所以在代码 中我不再使用泛型
private int partition(int[] arr, int l, int r, Random rnd){// 生成 [l, r] 之间的随机索引int p l rnd.nextInt(r - l 1);swap(arr, l, p);// arr[l1...i-1] v; arr[j1...r] vint i l 1, j r;while(true){while(i j arr[i] arr[l])i ;while(j i arr[j] arr[l])j --;if(i j) break;swap(arr, i, j);i ;j --;
}swap(arr, l, j);return j;
}
private void swap(int[] arr, int i, int j){int t arr[i];arr[i] arr[j];arr[j] t;
}
有了 partition我们的 selectK 的主题逻辑非常简单。
首先进行 partition假设结果是 p。我们只需要将 k 和 p 做比较。
如果 k p直接返回 arr[p] 即可如果 k p在 arr[l, p - 1] 的范围继续找即调用 selectK(arr, l, p - 1, k, rnd)如果 k p在 arr[p 1, r] 的范围继续找即调用 selectK(arr, p 1, r, k, rnd)
就有了下面的代码
private int selectK(int[] arr, int l, int r, int k, Random rnd){
int p partition(arr, l, r, rnd);
if(k p) return arr[p];
if(k p) return selectK(arr, l, p - 1, k, rnd);return selectK(arr, p 1, r, k, rnd);
}
这样我们就完成了 select K 的过程。是不是非常简单
下面我们用我们写的 select K先来解决 Leetcode 上第 215 号问题
这个问题是求第 k 大元素但是我们的 selectK 求得是第 k 小元素。怎么办 非常简单我们只需要在调用 select K 之前将求第 k 大元素的这个 k转换成 对应求的是第几小元素对应的索引就好了。 按照题目描述如果 k 是 1对应就是要找最大元素那么相应的我们的 select K 的索引就是 nums.length - 1。如果10个数K1第一个最大的数就是SelectK索引为9的那个的元素 如果 k 是 nums.length其实就是求最小元素那么相应的我们的 selectK 的 索引就是 0。 如果10个数第10个最大的数就是SelectK索引为0的那个的元素最小值 他们之间的转换关系是 nums.length - k。 力扣215.数组中的第K个最大元素
给定整数数组 nums 和整数 k请返回数组中第 k 个最大的元素。
请注意你需要找的是数组排序后的第 k 个最大的元素而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。 import java.util.Random; //导入Random包
class Solution {public int findKthLargest(int[] nums, int k) {//只有两行其他的内容全部复用我们上面实现的 selectK是不是很酷//我们的SelectK是第K最小元素所以这里findKthLargest传入下标要处理一下//转换关系是 nums.length - kRandom rnd new Random();return selectK(nums, 0, nums.length - 1, nums.length - k, rnd);}//有了 partition我们的 selectK 的主题逻辑非常简单。private int selectK(int[] arr, int l, int r, int k, Random rnd){//首先进行 partition假设返回值结果是 p。我们只需要将 k 和 p 做比较。int p partition(arr, l, r, rnd); //如果 k p直接返回 arr[p] 即可if(k p) return arr[p]; //如果 k p在 arr[l, p - 1] 的范围继续找即调用 selectK(arr, l, p - 1, k, rnd)if(k p) return selectK(arr, l, p - 1, k, rnd); //如果 k p在 arr[p 1, r] 的范围继续找即调用 selectK(arr, p 1, r, k, rnd)return selectK(arr, p 1, r, k, rnd);
}private int partition(int[] arr, int l, int r, Random rnd){// 生成 [l, r] 之间的随机索引int p l rnd.nextInt(r - l 1);swap(arr, l, p);// arr[l1...i-1] v; arr[j1...r] vint i l 1, j r;while(true){while(i j arr[i] arr[l])i ;while(j i arr[j] arr[l])j --;if(i j) break;swap(arr, i, j);i ;j --;}swap(arr, l, j);return j;}//数组指定索引两数交换private void swap(int[] arr, int i, int j){int t arr[i];arr[i] arr[j];arr[j] t;}
}
