目录
一、分治简介
分治：分而治之，就是将一个大问题拆分为多个小问题，逐一解决。
二、75.颜⾊分类
题目链接：75.颜⾊分类
题目描述：
题目解析：
- 就是给一个只含0 1 2 的数组，排序。
解题思路：
- 我们使用3个指针将数组分为4段。
- [ 0, left - 1 ]里面是0，[ left , i - 1]是1，[ i , right ]是待排序区，[ right + 1 , nums.length - 1 ]是2。
- 当nums[ i ] 为0的时候，就需要将nums[ i ] 与nums[ left ]交换，并且left 和 i 都要向后走一步，因为nums[ left ]是1，就算left = i使得nums[ left ] 是0，逻辑也一样。
- 当nums[ i ] 为1的时候，直接 i 向后走一步即可。
- 当nums[ i ] 为2的时候，就需要将nums[ i ] 与nums[ right ]交换，并且right要向后走一步，而 i 不走。
解题代码：
//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
public void sortColors(int[] nums) {
int left = 0;
int right = nums.length - 1;
//数组分三块[ 0, left - 1 ]，[ left , right ]，[ right + 1 , nums.length - 1 ]
for(int i = 0; i <= right; i++) {
if(nums[i] == 0) swap(nums,left++,i);
else if(nums[i] == 2) swap(nums,right--,i--);
}
}
public void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
三、912.排序数组
题目链接：912.排序数组
题目描述：
题目解析：
- 给数组排序。
解题思路：
- 我们使用快排来解决，并且使用 3指针 + 随机选取基准。
- 随机选取基准：在要排序区间中等可能得随机抽取一个元素来当基准值，nums[new Random().nextInt(right - left + 1) + left];
- 3指针，跟上面颜色分类思路一样。
- [ l , r ]是待排序区间， [ l , left - 1 ]里面是小于基准值的数，[ left , i - 1]是等于基准值的数，[ i , right ]是待排序区，[ right + 1 , r ]是大于基准值的数。
- 当nums[ i ] 为小于基准值的时候，就需要将nums[ i ] 与nums[ left ]交换，并且left 和 i 都要向后走一步，因为nums[ left ]是等于基准值，就算left = i使得nums[ left ] 是小于基准值，逻辑也一样。
- 当nums[ i ] 为等于基准值的时候，直接 i 向后走一步即可。
- 当nums[ i ] 为大于基准值的时候，就需要将nums[ i ] 与nums[ right ]交换，并且right要向后走一步，而 i 不走。
- 在排序[ l , left - 1]和[right + 1 , r]区间即可。
解题代码：
//时间复杂度：O(n)
//空间复杂度：O(1)
import java.util.*;
class Solution {
public int[] sortArray(int[] nums) {
quickSort(nums, 0 , nums.length - 1);
return nums;
}
//快排
public void quickSort(int[] nums, int l, int r) {
if(l >= r) return;
int left = l;
int right = r;
//随机找基准
int key = nums[new Random().nextInt(right - left + 1) + left];
//数组分三块[ l, left - 1 ]，[ left , right ]，[ right + 1 , r ]
for(int i = left; i <= right; i++) {
if(nums[i] < key) swap(nums,left++,i);
else if(nums[i] > key) swap(nums,right--,i--);
}
quickSort(nums,l,left-1);
quickSort(nums,right+1,r);
}
public void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
四、215.数组中的第K个最⼤元素
题目链接：215.数组中的第K个最⼤元素
题目描述：
题目解析：
- 返回数组中第k大的数。
4.1 快排思想
解题思路：
- 我们使用上面的快排思想，只要在分个类讨论第k大的数在哪个区间即可。
- 当[ right + 1 , r ]区间中包含要找的数，直接在调用即可。
- 当[ left , right ]区间中包含要找的数，直接返回基准值。
- 当[ l, left - 1 ]区间中包含要找的数，调用是，传参就是在该区间找区间中（第k- 前两区间长度）的数。
解题代码：
//时间复杂度：O(n)
//空间复杂度：O(1)
import java.util.*;
class Solution {
public int findKthLargest(int[] nums, int k) {
return qsort(nums,0,nums.length-1,k);
}
//快排返回第k大的数。
public int qsort(int[] nums, int l, int r, int k) {
int left = l;
int right = r;
//随机找基准
int key = nums[ new Random().nextInt(r - l + 1) + l];
//数组分三块[ l, left - 1 ]，[ left , right ]，[ right + 1 , r ]
for(int i = left; i <= right; i++) {
if(nums[i] < key) swap(nums,left++,i);
else if(nums[i] > key) swap(nums,right--,i--);
}
//每个区间的长度
int litLength = left - l;
int midLength = right - left + 1;
int bigLength = r - right;
//分类讨论
if(bigLength >= k) return qsort(nums, right+1, r, k);
else if(midLength + bigLength >= k) return key;
else return qsort(nums, l, left-1, k- midLength - bigLength);
}
public void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
4.2 堆排序思想
解题思路：
- 直接使用一个堆，将数组放进堆中，
- 由于库函数创建的是小根堆，所以我们返回第nums.length - k + 1小的数即可。
//时间复杂度：O(NlogK)
//空间复杂度：O(n)
import java.util.*;
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> queue = new PriorityQueue<>();
for(int i = 0; i < nums.length; i++) {
queue.add(nums[i]);
}
int ret = 0;
for(int i = 0; i < nums.length - k + 1; i++) {
ret = queue.poll();
}
return ret;
}
}
4.3 排序
解题思路：
- 直接调用库函数将数组排序，返回即可。
//时间复杂度：O(NlogN)
//空间复杂度：O(logN)
import java.util.*;
class Solution {
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}
}
五、LCR159.库存管理 |||
题目链接：LCR159.库存管理 |||
题目描述：
题目解析：
- 其实就是返回数组中前k个最小的数的集合
5.1 快排思想
解题思路：
- 我们使用上面的快排思想，只要在分个类讨论第k大的数在哪个区间即可。
- 当[ l, left - 1 ]区间中包含要找的数，直接在调用即可。
- 当[ left , right ]区间中包含要找的数，直接返回。
- 当[ right + 1 , r ]区间中包含要找的数，调用是，传参就是在该区间找区间中（第k- 前两区间长度）的数。
- 细节处理：这里的cnt是可以等于0和数组长度的，单独考虑，等于0返回空数组，等于数组长度，返回整个数组即可。
解题代码：
//时间复杂度：O(N)
//空间复杂度：O(cnt)
import java.util.*;
class Solution {
public int[] inventoryManagement(int[] nums, int cnt) {
//特殊情况
if(cnt == 0) return new int[]{};
if(cnt == nums.length) return nums;
qsort(nums, 0, nums.length-1, cnt);
int[] ret = new int[cnt];
for(int i = 0; i < cnt; i++)
ret[i] = nums[i];
return ret;
}
//快排
public void qsort(int[] nums, int l, int r, int k) {
int left = l;
int right = r;
int key = nums[new Random().nextInt(r-l+1)+l];
//数组分三块[ l, left - 1 ]，[ left , right ]，[ right + 1 , r ]
for(int i = l; i <= right; i++) {
if(nums[i] < key) swap(nums, left++, i);
else if(nums[i] > key) swap(nums,right--, i--);
}
//每个区间的长度
int litLength = left - l;
int midLength = right - left + 1;
int bigLength = r - right;
//分类讨论
if(litLength >= k) qsort(nums, l, left-1, k);
else if(litLength+midLength >= k) return;
else qsort(nums,right+1, r, k-litLength-midLength);
}
public void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
5.2 堆排序思想
解题思路：
- 直接使用一个堆，将数组放进堆中，
- 由于库函数创建的是小根堆，所以我们返回前cnt个数数即可。
解题代码：
//时间复杂度：O(NlogCNK)
//空间复杂度：O(n)
import java.util.*;
class Solution {
public int[] inventoryManagement(int[] nums, int cnt) {
if(cnt == 0) return new int[]{};
if(cnt == nums.length) return nums;
PriorityQueue<Integer> queue = new PriorityQueue<>();
for(int i = 0; i < nums.length; i++)
queue.add(nums[i]);
int[] ret = new int[cnt];
for(int i = 0; i < cnt; i++) {
ret[i] = queue.poll();
}
return ret;
}
}
5.3 排序
解题思路：
- 直接调用库函数将数组排序，返回即可。
解题代码：
//时间复杂度：O(NlogN)
//空间复杂度：O(logN+cnk)
import java.util.*;
class Solution {
public int[] inventoryManagement(int[] nums, int cnt) {
if(cnt == 0) return new int[]{};
if(cnt == nums.length) return nums;
Arrays.sort(nums);
int[] ret = new int[cnt];
for(int i = 0; i < cnt; i++) {
ret[i] = nums[i];
}
return ret;
}
}