0.分治
分而治之
1.颜色分类
75. 颜色分类 - 力扣（LeetCode）
给定一个包含红色、白色和蓝色、共
n个元素的数组nums，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。我们使用整数
0、1和2分别表示红色、白色和蓝色。必须在不使用库内置的 sort 函数的情况下解决这个问题。
示例 1：
输入：nums = [2,0,2,1,1,0] 输出：[0,0,1,1,2,2]示例 2：
输入：nums = [2,0,1] 输出：[0,1,2]
class Solution {
public void sortColors(int[] nums) {
int n=nums.length;
int left=-1,right=n,i=0;
while(i<right){//i要扫描完
if(nums[i]==0){
swap(nums,++left,i++);
}else if(nums[i]==2){
swap(nums,--right,i);
}else{
i++;
}
}
}
public void swap(int[] nums,int x,int y){
int tmp=nums[x];
nums[x]=nums[y];
nums[y]=tmp;
}
}
2.快速排序
排序数组
给你一个整数数组 nums，请你将该数组升序排列。
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;
}
//数组分为三块
//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);
}
}
//[l,left],[left+1,right-1],[right,r]
qsort(nums,l,left);
qsort(nums,right,r);
}
public void swap(int[] nums,int x,int y){
int tmp=nums[x];
nums[x]=nums[y];
nums[y]=tmp;
}
}3.数组中的第k个最大元素
215. 数组中的第K个最大元素 - 力扣（LeetCode）
给定整数数组
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
class Solution {
public int findKthLargest(int[] nums, int k) {
return qsortchoice(nums, 0, nums.length - 1, k);
}
public int qsortchoice(int[] nums, int l, int r, int k) {
while (l == r) {
return nums[l];
}
// 随机在范围内选择对应的数字
// 随机选择一个基准元素
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);
}
}
// 快速选择的算法，分情况讨论
int b = right - left - 1, c = r - right + 1;
if (c >= k) {
return qsortchoice(nums, right, r, k);
} else if (b + c >= k) {
return key;
} else {
return qsortchoice(nums, l, left, k - b - c);
}
}
public void swap(int[] nums, int x, int y) {
int tmp = nums[x];
nums[x] = nums[y];
nums[y] = tmp;
}
}4.最小的K个数
class Solution {
public int[] inventoryManagement(int[] nums, int k) {
qsortchoice(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 qsortchoice(int[] nums, int l, int r, int k) {
while (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);
}
}
// 快速选择的算法，分情况讨论
int a=left-l+1,b=right-1-left-1+1;
if (a>k) {
qsortchoice(nums, l, left, k);
} else if (a + b >= k) {
return;
} else {
qsortchoice(nums, right,r, k - a-b);
}
}
public void swap(int[] nums, int x, int y) {
int tmp = nums[x];
nums[x] = nums[y];
nums[y] = tmp;
}
}5.归并排序
912. 排序数组 - 力扣（LeetCode）
在递归的时候如果总是需要new一个变量，这是我们可以把这个变量作为全局变量。
class Solution {
int[] tmp;//定义全局变量，就不用反复new了
public int[] sortArray(int[] nums) {
tmp=new int[nums.length];
mergeSort(nums,0,nums.length-1);
return nums;
}
public void mergeSort(int[] nums,int left,int right){
if(left>=right){
return;
}
//1.根据中间点划分区间
int mid=(left+right)/2;
//[left,mid][mid+1,right]
//2.先把左右区间排个序
mergeSort(nums,left,mid);
mergeSort(nums,mid+1,right);
//3.合并两个有序数组
int cur1=left,cur2=mid+1,i=0;
while(cur1<=mid&&cur2<=right){
tmp[i++]=nums[cur1]<=nums[cur2]?nums[cur1++]:nums[cur2++];
}
//处理没有遍历完的数组
while(cur1<=mid){
tmp[i++]=nums[cur1++];
}
while(cur2<=right){
tmp[i++]=nums[cur2++];
}
//还原到nums数组上
for(int j=left;j<=right;j++){
nums[j]=tmp[j-left];
}
}
}6.数组中的逆序对
LCR 170. 交易逆序对的总数 - 力扣（LeetCode）
class Solution {
int[] tmp;
public int reversePairs(int[] record) {
int n=record.length;
tmp=new int[n];
return mergeSort(record,0,n-1);
}
public int mergeSort(int[] nums,int left,int right){
while(left>=right){
return 0;
}
int ret=0;
//选择一个中间点，将数组进行划分
int mid=(left+right)/2;
//[left,mid][mid+1,right]
//2.左半部分的个数+右半部分的个数+排序
ret=ret+mergeSort(nums,left,mid);
ret=ret+mergeSort(nums,mid+1,right);
//3.一左一右的个数
int cur1=left,cur2=mid+1,i=0;
while(cur1<=mid&&cur2<=right){
if(nums[cur1]<=nums[cur2]){
tmp[i++]=nums[cur1++];
}else{
ret=ret+mid-cur1+1;
tmp[i++]=nums[cur2++];
}
}
//4.处理一下后面的排序
while(cur1<=mid){
tmp[i++]=nums[cur1++];
}
while(cur2<=right){
tmp[i++]=nums[cur2++];
}
for(int j=left;j<=right;j++){
nums[j]=tmp[j-left];
}
return ret;
}
}7.计算右侧⼩于当前元素的个数(难点)
315. 计算右侧小于当前元素的个数 - 力扣（LeetCode）
class Solution {
int[] ret;
int[] index; // 标记 nums 中当前元素的原始下标
int[] tmpIndex;
int[] tmpNums;
public List<Integer> countSmaller(int[] nums) {
int n = nums.length;
ret = new int[n];
index = new int[n];
tmpIndex = new int[n];
tmpNums = new int[n];
// 初始化 index 数组
for (int i = 0; i < n; i++) {
index[i] = i;
}
mergeSort(nums, 0, n - 1);
List<Integer> l = new ArrayList<Integer>();
for (int x : ret) {
l.add(x);
}
return l;
}
public void mergeSort(int[] nums, int left, int right) {
if (left >= right) {
return;
}
// 1. 根据中间元素划分区间
int mid = (left + right) / 2;
// [left, mid] [mid + 1, right]
// 2. 处理左右两个区间
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
// 3. 处理⼀左⼀右的情况
int cur1 = left, cur2 = mid + 1, i = 0;
while (cur1 <= mid && cur2 <= right) { // 降序排序
if (nums[cur1] <= nums[cur2]) {
tmpNums[i] = nums[cur2];
tmpIndex[i++] = index[cur2++];
} else {
ret[index[cur1]] += right - cur2 + 1; // 重点
tmpNums[i] = nums[cur1];
tmpIndex[i++] = index[cur1++];
}
}
// 4. 处理剩余的排序⼯作
while (cur1 <= mid) {
tmpNums[i] = nums[cur1];
tmpIndex[i++] = index[cur1++];
}
while (cur2 <= right) {
tmpNums[i] = nums[cur2];
tmpIndex[i++] = index[cur2++];
}
for (int j = left; j <= right; j++) {
nums[j] = tmpNums[j - left];
index[j] = tmpIndex[j - left];
}
}
}8.翻转对
给定一个数组
nums，如果i < j且nums[i] > 2*nums[j]我们就将(i, j)称作一个重要翻转对。你需要返回给定数组中的重要翻转对的数量。
示例 1:
输入: [1,3,2,3,1] 输出: 2示例 2:
输入: [2,4,3,5,1] 输出: 3注意:
- 给定数组的长度不会超过
50000。- 输入数组中的所有数字都在32位整数的表示范围内。
class Solution {
int[] tmp;
public int reversePairs(int[] nums) {
int n = nums.length;
tmp = new int[n];
return mergeSort(nums, 0, n - 1);
}
public int mergeSort(int[] nums, int left, int right) {
if (left >= right)
return 0;
int ret = 0;
// 1. 根据中间元素，将区间分成两部分
int mid = (left + right) / 2;
// [left, mid] [mid + 1, right]
// 2. 求出左右两个区间的翻转对
ret += mergeSort(nums, left, mid);
ret += mergeSort(nums, mid + 1, right);
// 3. 处理⼀左⼀右 - 先计算翻转对
int cur1 = left, cur2 = mid + 1, i = left;
// 降序版本
while (cur1 <= mid) {
while (cur2 <= right && nums[cur2] >= nums[cur1] / 2.0)
cur2++;
if (cur2 > right)
break;
ret += right - cur2 + 1;
cur1++;
}
// 4. 合并两个有序数组
cur1 = left;
cur2 = mid + 1;
while (cur1 <= mid && cur2 <= right)
tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur2++] : nums[cur1++];
while (cur1 <= mid)
tmp[i++] = nums[cur1++];
while (cur2 <= right)
tmp[i++] = nums[cur2++];
for (int j = left; j <= right; j++)
nums[j] = tmp[j];
return ret;
}
}
