我的学习笔记

分治是分而治之，它是将一个大的问题拆分为若干的相同/相似的小问题，而这些小问题是可以快速地解决的，从而推广到解决大问题

它分为两个模块：快排和归并

快排

LC75. 颜色分类

这个是把这个数组分为四个部分，需要使用三个指针

定义三个指针 left, i, right

[0, left]: 全是 0 的数
[left + 1, i - 1]: 全是 1
[i, right - 1]: 待遍历的未知数
[right, n - 1]: 全是 2

然后考虑细节就可以了：

nums[i] == 0: 只需要把 left + 1 和 i 位置交换一下，然后 left++, i++ 即可
nums[i] == 1: 不需要经行任何交换，只要 i++ 就可以了
nums[i] == 2: 把 right - 1 和 i 位置交换，把 right-- 就可以了
i 不能加 1, 因为交换完后，i 的位置依然是未知数

最后只需要考虑初识情况就可以了：为了满足那些区间内的情况，left 必须为 -1, right 必须为 n

Java

public void sortColors(int[] nums) {
	/**
	定义三个指针 left, i, right 
		[0, left]: 全是 0 的数 
		[left + 1, i - 1]: 全是 1
		[i, right - 1]: 待遍历的未知数
		[right, n - 1]: 全是 2
	*/ 
	// 为了满足上面的条件 left 必须从 -1 开始，right 必须从 n 开始
	int left = -1, i = 0, n = nums.length, right = n;

	while (i < right) {
		if (nums[i] == 0) {
			// 把 left + 1 和 i 的位置交换, i++, left++
			swap(++left, i++, nums);
		} else if (nums[i] == 1) {
			// 不需要交换，i++ 就可以
			i++;
		} else {
			// nums[i] == 2 把后面的 right - 1 与 i 交换，由于 right - 1 的内容是没有处理过的，因此 i 不需要加 1
			swap(i, --right, nums);
		}
	}
}

private void swap(int i, int j, int[] arr) {
	int tmp = arr[i];
	arr[i] = arr[j];
	arr[j] = tmp;
}

LC912. 排序数组-快排

这个题目需要有 LC75. 颜色分类这个基础，因为快排中元素的优化就是需要涉及到这道题目的思想

思路：

随机找到一个数 randomNum，把小于这个数的放在一堆，等于这个数的放在一堆，大于这个数的放在一堆
- [start, left]: 小于 randomNum
- [left + 1, i - 1]: 等于 randomNum
- [i, right - 1]: 未知
- [right, end]: 大于 randomNum
随机找一个数可以让它的时间复杂度趋于 $N%20%5Ctimes%20%5Clog_%7BN%7D$
然后进行分治，由于等于 randomNum 的数已经排序好，那么就只需要再排序 [start, left] 和 [right, end] 这两个区间就可以了

Java

Random random = new Random();

public int[] sortArray(int[] nums) {
	qsort(0, nums.length - 1, nums);

	return nums;
}

// 排序 [start, end] 内的元素
private void qsort(int start, int end, int[] nums) {
	if (start >= end) return;
	// 先随机获取一个元素
	int randomNum = nums[random.nextInt(start, end + 1)];
	/**
	[0, left]: < randomNum
	[left + 1, i - 1]: = randomNum
	[i, right - 1]: 未知
	[right, n]: > randomNum
	*/
	int left = start - 1, i = start, right = end + 1;
	while (i < right) {
		if (nums[i] < randomNum) {
			swap(++left, i++, nums);
		} else if (nums[i] == randomNum) {
			i++;
		} else {
			// nums[i] > randomNum
			swap(i, --right, nums);
		}
	}

	// 元素值为 randomNum 已经排序好，那么就需要排序前后两个区间了
	qsort(start, left, nums);
	qsort(right, end, nums);
}

private void swap(int i, int j, int[] nums) {
	int t = nums[i];
	nums[i] = nums[j];
	nums[j] = t;
}

LC215. 数组中的第K个最大元素

这个题目是对 LC912. 排序数组-快排扩展。

思路：

前面一部分是执行 LC912. 排序数组-快排，把它分为三个部分
- [start, left]: 小于 randomNum
- [left + 1, i - 1]: 等于 randomNum
- [i, right - 1]: 未知
- [right, end]: 大于 randomNum
然后就可以根据条件来递归
- 右边那块区间长度大于 k，说明 k 就在右边那块区间内，那么就只需要处理右边那一部分就可以了
- 如果上面条件不满足，那么就可以找一下中间的那块区间，如果右边的区间加中间区间的长度比 k 大，那么 k 就在中间那块区间内，直接返回就可以了
- 如果都不满足，那么就在左边那块区间，但是在处理左边那块区间的时候，需要把 k 减去中间和右边区间长度之和，因为题目要求是求第 k 大的值

Java

Random random = new Random();
public int findKthLargest(int[] nums, int k) {
	return qoption(0, nums.length - 1, nums, k);
}


public int qoption(int l, int r, int[] nums, int k) {
	if (l > r) return -1;
	// random.nextInt(l, r + 1)
	int randomNum = nums[r];

	/**
	先遍历一次，把它分为这几个部分
		[l, left]: < randomNum
		[left + 1, i - 1]: = randomNum
		[i, right - 1]: 未知
		[right, r]: > randomNum
	*/
	int left = l - 1, i = l, right = r + 1;
	while (i < right) {
		if (nums[i] < randomNum) swap(++left, i++, nums);
		else if (nums[i] == randomNum) i++;
		else swap(i, --right, nums);
	}

	// 根据条件，判断它是否是第 k 个元素，然后递归
	if (r - right + 1 >= k) return qoption(right, r, nums, k); // 右边区间长度大于等于 k 
	else if (r - left >= k) return nums[right - 1]; // 说明 k 在中间的那段区间
	else return qoption(l, left, nums, k - (r - left)); // 在左边那段区间, 因为去掉了 
}


private void swap(int i, int j, int[] nums) {
	int t = nums[i];
	nums[i] = nums[j];
	nums[j] = t;
}

LCR 159. 库存管理 III

这倒题目和 LC215. 数组中的第K个最大元素类似，需要有 LC912. 排序数组-快排这个相关的知识点

思路：

先遍历一次，分为三块
- [start, left]: 小于 randomNum
- [left + 1, i - 1]: 等于 randomNum
- [i, right - 1]: 未知
- [right, end]: 大于 randomNum
根据情况来筛选出对应的条件
- 在左侧的区间，那么还需要遍历一次，但是不需要排序中间和右侧的区间了
- 在中间的区间（包含左侧区间的最右边和右侧区间的最左边），那么就可以直接返回
- 在右侧区间，那么依然还需要遍历一次，但是 cnt 就需要减去相关的元素了

Java

Random random = new Random();

public int[] inventoryManagement(int[] stock, int cnt) {
	int end = quickSelect(0, stock.length - 1, stock, cnt);

	int[] result = new int[cnt];
	for(int i = 0; i < end; i++) result[i] = stock[i];

	return result;
}

private int quickSelect(int l, int r, int[] nums, int cnt) {
	if (l > r) {
		return -1;
	}
	// int randomNum = nums[random.nextInt(l, r + 1)];
	int randomNum = nums[r];
	int left = l - 1, i = l, right = r + 1;
	while (i < right) {
		if (randomNum > nums[i]) swap(i++, ++left, nums); 
		else if (randomNum == nums[i]) i++;
		else swap(--right, i, nums);
	}
	// [l, left]: < randonNum  [left + 1, right - 1]: == randonNum
	if (left - l + 1 > cnt) return quickSelect(l, left, nums, cnt);
	else if (right - l >= cnt) return cnt + l;
	else return quickSelect(right, r, nums, cnt - (right - l));
}

private void swap(int i, int j, int[] nums) {
	int t = nums[i];
	nums[i] = nums[j];
	nums[j] = t;
}

归并

归并和快排很像的。

快排是先排再分：先确定元素的位置，然后一个区间一个区间来排序，类似与二叉树的前序遍历

归并是先分再排：先分到不能分为止，分到只有两个元素为止（一个元素是直接返回，不需要排序），然后把那两块区间看为两个有序的数组，类似二叉树的后续遍历

LC912. 排序数组-归并

这个题目归并排序的一个入门题目，思路就是归并排序的思路（上面刚刚讲述过，这里就不复述了）。

在做之后的归并的题目之前，必须要对这个题目的题解很熟悉，因为后面题目都是以这个题目为基础的

Java

public int[] sortArray(int[] nums) {
	mergeSort(0, nums.length - 1, nums);
	return nums;
}

private void mergeSort(int l, int r, int[] nums) {
	if (r <= l) return; // 只有一个元素，那么就不需要排序了
	
	int mid = (r - l) / 2 + l;

	// 先排左边，再排右边
	mergeSort(l, mid, nums);
	mergeSort(mid + 1, r, nums);

	// 合并两个有序数组
	int[] tmp = new int[r - l + 1];
	int lIndex = l, rIndex = mid + 1, tIndex = 0;
	for (; lIndex <= mid && rIndex <= r; ) {
		if (nums[lIndex] < nums[rIndex]) tmp[tIndex++] = nums[lIndex++];
		else tmp[tIndex++] = nums[rIndex++];
	}

	// 处理残留项
	while (lIndex <= mid) tmp[tIndex++] = nums[lIndex++];
	while (rIndex <= r) tmp[tIndex++] = nums[rIndex++];
	// 把 tmp 赋值回去
	tIndex = 0;
	for (int i = l; i <= r; i++) nums[i] = tmp[tIndex++];
}

LCR 170. 交易逆序对的总数

这个需要熟悉 LC912. 排序数组-归并不然会比较难以理解

思路：

先计算左边那块区间的所有符合条件的值，然后计算右边那块区间的所有符合条件的值，最后在左右两边各个取一个，计算出符合条件的值，然后相加起来（这样是和分治的思想一样）
分治-归并-LCR170.交易逆序对的总数
两边各取一个：这个题目是可以用升序也可以采用降序。就以升序为例
- 当 record[cur1] > record[cur2] 的时候，发现在 [left, cur1 -1] 这个区间内的值都是比 record[cur2] 小，而在 [cur1, mid] 这个区间内的值都是要比 record[cur2] 大，因此从 record[cur2] 视角来看，它是已经可以算出所有比它大的情况了
- 当 record[cur1] <= record[cur2] 的时候，你不能计算出比它大的情况，因此只需要赋值给临时数组就可以了
计算左边或者右边：通过分治的思想来理解就可以了

由于题目是要求获取到 左侧比右侧大 这样的情况，所以只会在 record[cur1] > record[cur2] 这样的情况下 result 才会增加

Java

int[] tmp;

public int reversePairs(int[] record) {
	tmp = new int[record.length];
	return mergeSort(0, record.length - 1, record);
}

private int mergeSort(int left, int right, int[] record) {
	if (right <= left) return 0;
	
	// 先算左侧，再算右侧
	int mid = (right - left) / 2 + left;
	int leftCount = mergeSort(left, mid, record);
	int rightCount = mergeSort(mid + 1, right, record);

	int result = rightCount + leftCount;


	int cur1 = left, cur2 = mid + 1, tmpIndex = 0;
	while (cur1 <= mid && cur2 <= right) {
		// 排序(升序的写法)
		// if (record[cur1] <= record[cur2]) {
		//     tmp[tmpIndex++] = record[cur1++];
		// } else {
		//     // record[cur1] > record[cur2]
		//     // [cur1, mid] 内的值都比 record[cur2] 大，并且 [left, cur1) 内的值都比 record[cur2] 小。那就没有缺失了
		//     result += mid - cur1 + 1;
		//     tmp[tmpIndex++] = record[cur2++];
		// }

		// 降序的写法
		if (record[cur1] > record[cur2]) { 
			// 说明之前的内容都比 record[cur1] 大，但是 record[cur1] 要比 [cur2, right] 区间内的值都要大
			result += right - cur2 + 1;
			tmp[tmpIndex++] = record[cur1++];
		} else tmp[tmpIndex++] = record[cur2++]; // record[cur1] <= record[cur2]
	}

	// 至少有一边是走完了，那就不可能还有其他的多余的值可以加到 result 上面
	while (cur1 <= mid) tmp[tmpIndex++] = record[cur1++];
	while (cur2 <= right) tmp[tmpIndex++] = record[cur2++];

	// 赋值到 record
	tmpIndex = 0;
	for (int i = left; i <= right; i++) {
		record[i] = tmp[tmpIndex++]; 
	}
	return result;
}

LC315. 计算右侧小于当前元素的个数

这个题目和 LCR 170. 交易逆序对的总数很像，都是要求逆序对，只不过之前的那道题目是求和，而这道题目是求每个元素对应的逆序对。

由于题目是求左侧那一块的逆序对，如果采用升序的做法，会比较麻烦，因此采用降序的做法。

升序是在右侧求，然后在左侧寻找，找出比它大的元素个数，然后累加，这个和题目中求左侧的有点出入。
而降序是刚好相反，是在左侧求，寻找右侧比它大的元素之和，这个刚好满足题目的要求，因此选择降序

但是由于原先的数组会排序，因此原来的数组的下标会变化，如果想要找出原来的下标，是不能直接求出来的，需要用一个数据结构来存储

“原来的值-对应的下标” 这就很自然的想到了 Hash 表，但是由于值是可以重复的，因此直接使用 Hash 表是不太合适的，但是可以利用它的思想，创建出 “当前元素的下标-原来元素的下标” 这样的 Hash 表。

只有在最后“合并两个有序数组”的时候下标才会变化，因此也是在这个时候来修改。
而如果在原来的位置上修改比较复杂，因此还需要创建一个临时表来存储对应的下标

Java

int[] tmpNums; 
int[] tmpIndexs; 

public List<Integer> countSmaller(int[] nums) {
	int n = nums.length;
	List<Integer> result = new ArrayList<>(n);
	tmpNums = new int[n];
	tmpIndexs = new int[n];

	// indexs 表示 nums 元素所对应的下标, 把 result 添加元素
	int[] indexs = new int[n];
	for (int i = 0; i < n; i++) {
		indexs[i] = i;
		result.add(0);
	}

	mergeSort(0, n - 1, nums, indexs, result);

	return result;
}

private void mergeSort(int left, int right, int[] nums, int[] indexs,List<Integer> result) {
	if (left >= right) return;

	int mid = (right - left) / 2 + left;
	
	mergeSort(left, mid, nums, indexs, result);
	mergeSort(mid + 1, right, nums, indexs, result);

	// 降序排序 + 计算 + 移动 indexs
	int tmpNumsIndex = 0, tmpIndexsIndex = 0, leftIndex = left, rightIndex = mid + 1;
	while (leftIndex <= mid && rightIndex <= right) {
		if (nums[leftIndex] > nums[rightIndex]) {
			// 计算出 leftIndex 对应的真实的下标
			int index = indexs[leftIndex];
			result.set(index, result.get(index) + right - rightIndex + 1); // 累加
			tmpNums[tmpNumsIndex++] = nums[leftIndex++];
			tmpIndexs[tmpIndexsIndex++] = index; // 把 nums[leftIndex] 对应的下标存储起来
		} else {
			// nums[leftIndex] <= nums[rightIndex]
			tmpIndexs[tmpIndexsIndex++] = indexs[rightIndex]; // 把 nums[rightIndex] 对应的下标存储起来
			tmpNums[tmpNumsIndex++] = nums[rightIndex++];
		}
	}

	// 处理残留内容
	while (leftIndex <= mid) {
		tmpIndexs[tmpIndexsIndex++] = indexs[leftIndex];
		tmpNums[tmpNumsIndex++] = nums[leftIndex++];
	} 
	while (rightIndex <= right) {
		tmpIndexs[tmpIndexsIndex++] = indexs[rightIndex]; // 把 nums[rightIndex] 对应的下标存储起来
		tmpNums[tmpNumsIndex++] = nums[rightIndex++];
	}

	// 把元素赋值给 indexs, nums
	tmpNumsIndex = 0;
	for (int i = left; i <= right; i++) {
		nums[i] = tmpNums[tmpNumsIndex++];
	}

	tmpIndexsIndex = 0;
	for (int i = left; i <= right; i++) {
		indexs[i] = tmpIndexs[tmpIndexsIndex++];
	}
}

LC493. 翻转对

这个题目是思路也是和前面的和 LCR 170. 交易逆序对的总数很像，只不过 result 添加的时机变了。

由于 mergeSort 完后，它是一个有序的数组，因此可以考虑使用同向双指针来处理这个情况（以降序为例）

遍历到 nums[cur1] > nums[cur2] * 2 的条件，可以直接计算 result 的结果 (result += right - cur2 + 1)
计算完后，cur1 的情况已经处理完了，执行 cur1++
此时 cur2 不需要从 mid + 1 开始，因为当前 nums[cur1] 的值一定不会大于 nums[cur2] \* 2
如果是 nums[cur1] <= nums[cur2] * 2 说明 cur2 不符合，执行 cur2++
反复执行 1/2/3/4 这个循环就可以了

由于条件和归并排序有出入，那么就不能像之前的那些题目一样，可以一边归并，一边求结果。这道题目只能把归并和求结果给分开

Java

int[] tmpNums;

public int reversePairs(int[] nums) {
	int n = nums.length;
	tmpNums = new int[n];
	return mergeSort(0, n - 1, nums);
}

private int mergeSort(int left, int right, int[] nums) {
	if (left >= right) return 0;

	int mid = (right - left) / 2 + left;
	int result = 0;
	result += mergeSort(left, mid, nums);
	result += mergeSort(mid + 1, right, nums);
	
	// 计算 result 的结果, 此时 [left, mid] 和 [mid + 1, right] 是两个有序数组
	int cur1 = left, cur2 = mid + 1;
	while (cur1 <= mid && cur2 <= right) {
		// // 升序
		// if (nums[cur1] > nums[cur2] * 2l) { // 要写为 2l 不然会溢出
		//     result += mid - cur1 + 1;
		//     cur2++;
		// } else cur1++; // nums[cur1] <= nums[cur2]

		// 降序
		if (nums[cur1] > nums[cur2] * 2l) { // 要写为 2l 不然会溢出
			result += right - cur2 + 1;
			cur1++;
		} else cur2++; // nums[cur1] <= nums[cur2]
	}
	// 排序
	cur1 = left;
	cur2 = mid + 1;
	int tmpIndex = 0;
	while (cur1 <= mid && cur2 <= right) {
		// if (nums[cur1] > nums[cur2]) tmpNums[tmpIndex++] = nums[cur2++]; // 升序
		if (nums[cur1] <= nums[cur2]) tmpNums[tmpIndex++] = nums[cur2++]; // 降序
		else tmpNums[tmpIndex++] = nums[cur1++];
	}
	while (cur1 <= mid) tmpNums[tmpIndex++] = nums[cur1++];
	while (cur2 <= right) tmpNums[tmpIndex++] = nums[cur2++];
	
	// 赋值
	tmpIndex = 0;
	for (int i = left; i <= right;) nums[i++] = tmpNums[tmpIndex++];

	return result;
}

Java研发系统课118期

JavaSE基础语法

Java数据结构

数据结构初阶

MySQL数据库

MySQL数据库基础

JavaEE

JavaEE初阶

JavaEE进阶

测试

Python基础课

Redis

RabbitMQ

LangChain&LangGraph-AI应用开发框架精品课

LangChain-AI应用开发框架精品课

OpenClaw AI 智能体深度介绍

算法精品课

优选算法

项目

抽奖系统

快排

LC75. 颜色分类

LC912. 排序数组-快排

LC215. 数组中的第K个最大元素

LCR 159. 库存管理 III

归并

LC912. 排序数组-归并

LCR 170. 交易逆序对的总数

LC315. 计算右侧小于当前元素的个数

LC493. 翻转对

JavaSE基础语法

Java数据结构

数据结构初阶

MySQL数据库

MySQL数据库基础

JavaEE

JavaEE初阶

JavaEE进阶

测试

LangChain-AI应用开发框架精品课

优选算法

抽奖系统

快排 ​

归并 ​

快排

归并