【Java 优选算法】分治 - 快速排序
欢迎关注个人主页：逸狼
创造不易，可以点点赞吗~
如有错误，欢迎指出~
分治算法就是将一个问题划分为多个相同类型的子问题,解决这些子问题即解决该类问题
颜色分类
题目链接
解法
利用三指针, i, left, right,将数组分为4个区间,如下图
三个指针的起始位置分别是
- left = -1 ,
- right = nums.length ,
- i =0
- 当nums[i]==0时,swap(nums[++left], nums[i++])
- 当nums[i]==1时,i++;
- 当nums[i]==2时,swap(nums[--right], nums[i]),记住此时的i还是未遍历元素,不能++
代码
class Solution {
public void sortColors(int[] nums) {
int n = nums.length;
int i = 0, left = -1, right = n;
while(i < right){
if(nums[i] == 0) swap(nums, i++, ++left);
else if(nums[i] == 1) i++;
else swap(nums, --right, i);
}
}
public void swap(int[] nums, int i, int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}排序数组
题目链接
解法
利用上一题的"数组分三块"的思想实现快排.
随机取数组的一个key作为基准值,以此将数组分为三部分,即小于key,等于key,和大于key三部分.
此时只有小于key和大于key的部分是乱序的,后面使用递归将这两部分也排成有序部分.
优化: 取随机数r,可以计算基准值: key=num[r % (right - left + 1) + left]
代码
class Solution {
public int[] sortArray(int[] nums) {
qsort(nums, 0, nums.length - 1);
return nums;
}
public void qsort(int[] nums, int l, int r){
if(l >= r) return;
//数组分三块
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);
}
//[l,left],[left +1, right - 1][right, r]
qsort(nums,l, left);
qsort(nums,right,r);
}
public void swap(int[] nums, int i, int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}数组中的第K个最大元素
题目链接
类似问题还有 前k大,前k小,第k大,第k小 问题
解法
解法一: 使用堆,使用小根堆
解法二: 数组分三块 + 随机选择基准元素
题目要求的是取出第k大的元素,我们记为t 根据数组分三块思想将数组根据基准值key分为三部分,每个部分元素个数是a,b,c, 分下面三种情况
- 当c >= k时,说明 t 一定在区间[right, r]
- 当b+c >= k时,说明 t 一定是key
- 当b+c+a >= k 时,说明 t在区间[l, left]
代码
class Solution {
public void swap(int[] nums, int i, int j){
int t = nums[i];
nums[i]= nums[j];
nums[j] = t;
}
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];
int left =l-1, i = l, right =r + 1, key = nums[new Random().nextInt(r - l + 1) + l];
while(i < right){
if(nums[i] < key) swap(nums, ++left, i++);
else if(nums[i] == key) i++;
else swap(nums, --right, i);
}
//计算每个区间的长度
int a = left - l + 1, b = right - left - 1, c = r - right + 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);
}
}库存管理|||
题目链接
解法
解法一: 排序,N*logN先将数组排序,再从小到大选择符合要求的元素
解法二:堆, N*log k ,建立一个大根堆
解法三: 快速选择算法,N, 随机选择基准元素+数组分三块,
下面展示解法三: 与上一题类似
代码
class Solution {
public void swap(int[] nums, int i, int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
public int[] inventoryManagement(int[] stock, int cnt) {
qsort(stock, 0, stock.length-1, cnt);
int[] ret = new int[cnt];
for(int i = 0; i < cnt; i++){
ret[i] = stock[i];
}
return ret;
}
public void qsort(int[] nums, int l, int r, int k){
if(l >= r) return;
int left = l - 1, right = r + 1, i = l, key = nums[new Random().nextInt(r - l + 1) + l];
while(i < right){
if(nums[i] < key) swap(nums, ++left, i++);
else if(nums[i] == key) i++;
else swap(nums, --right, i);
}
int a = left - l + 1, b = right - left - 1, c = r - right + 1;
if(a > k) qsort(nums, l, left, k);
else if(a + b >= k) return;
else qsort(nums, right, r, k - a - b);
}
}