引言：理解“不满足降序条件的数对”
在数组处理中，我们有时需要识别那些不符合特定排序规则的元素对。本教程关注的问题是：给定一个整数数组 hs，我们需要统计所有满足以下条件的数对 (hs[i], hs[j]) 的数量：
- i
- hs[i]
这类数对可以理解为在目标降序排列中出现的“逆序”对。例如，对于数组 hs = [7, 3, 5, 4, 1]：
- 3 小于 5 (且 3 在 5 之前)，形成一个不满足降序条件的数对 (3, 5)。
- 3 小于 4 (且 3 在 4 之前)，形成一个不满足降序条件的数对 (3, 4)。 因此，总数为 2。
再如 hs = [8, 5, 6, 7, 2, 1]：
- 5 小于 6，形成 (5, 6)。
- 5 小于 7，形成 (5, 7)。
- 6 小于 7，形成 (6, 7)。 总数为 3。
接下来，我们将介绍两种解决此问题的方法。
方法一：暴力枚举法 (O(N^2))
最直观的方法是使用两层嵌套循环，遍历所有可能的数对 (hs[i], hs[j]) 并检查它们是否满足条件。
算法思路
- 初始化一个计数器 count 为 0。
- 外层循环从数组的第一个元素 i = 0 遍历到倒数第二个元素 hs.length - 1。
- 内层循环从 j = i + 1 遍历到数组的最后一个元素 hs.length - 1。
- 在内层循环中，比较 hs[i] 和 hs[j]。如果 hs[i]
- 循环结束后，count 即为所需结果。
示例代码
public class ArrayPairCounter {
/**
* 使用暴力枚举法统计不满足降序条件的数对。
* 时间复杂度：O(N^2)
*
* @param hs 输入整数数组
* @return 不满足降序条件的数对数量
*/
public static int countBaadBruteForce(int[] hs) {
int count = 0;
for (int i = 0; i < hs.length; i++) {
for (int j = i + 1; j < hs.length; j++) {
// 比较当前位置 hs[i] 与其后的所有位置 hs[j]
if (hs[i] < hs[j]) {
// System.out.println("Found bad pair: (" + hs[i] + "," + hs[j] + ")"); // 可选：打印数对
count++;
}
}
}
return count;
}
public static void main(String[] args) {
int[] arr1 = {7, 3, 5, 4, 1};
System.out.println("Array: " + java.util.Arrays.toString(arr1) + ", Bad pairs: " + countBaadBruteForce(arr1)); // 预期输出 2
int[] arr2 = {8, 5, 6, 7, 2, 1};
System.out.println("Array: " + java.util.Arrays.toString(arr2) + ", Bad pairs: " + countBaadBruteForce(arr2)); // 预期输出 3
}
}优缺点
- 优点： 算法逻辑简单直观，易于理解和实现。
- 缺点： 时间复杂度为 O(N^2)，对于大型数组，性能会显著下降。
方法二：基于归并排序的优化算法 (O(N log N))
当数组规模较大时，O(N^2) 的暴力解法将无法满足性能要求。我们可以利用归并排序的特性，在 O(N log N) 的时间复杂度内完成计数。这种方法的核心在于归并（merge）阶段。
归并排序基础回顾
归并排序是一种分治算法：
- 分解 (Divide)： 将待排序数组分成两个大致相等的子数组。
- 解决 (Conquer)： 递归地对这两个子数组进行排序。
- 合并 (Combine)： 将两个已排序的子数组合并成一个完整的有序数组。
在合并两个已排序的子数组时，我们可以同时统计满足条件的数对。
计数原理
假设我们正在合并两个已经按照降序排列的子数组 l (左半部分) 和 r (右半部分)。我们的目标是统计原始数组中所有 hs[i]
当从 l 和 r 中选择元素合并到一个新的数组 a 时：
- 如果 l[lIdx] >= r[rIdx]：这意味着 l[lIdx] 应该在 r[rIdx] 之前（或相等），符合降序排列。我们将 l[lIdx] 放入 a，并继续处理 l 的下一个元素。此时，l[lIdx] 与 r[rIdx] 不构成我们定义的“不满足降序条件的数对”。
- 如果 l[lIdx]
通过在每次合并时累加这些计数，我们最终可以得到整个数组中不满足降序条件的数对总数。
代码实现
import java.util.Arrays; // 引入Arrays工具类用于打印和数组复制
public class MergeSortPairCounter {
/**
* 外部调用接口，用于统计不满足降序条件的数对。
* 为了避免修改原始数组，先复制一份。
*
* @param hs 输入整数数组
* @return 不满足降序条件的数对数量
*/
public static int countBaadMergeSort(int[] hs) {
// 复制数组以避免对原始数组的副作用
int[] tempArray = Arrays.copyOf(hs, hs.length);
return mergeSortAndCount(tempArray, tempArray.length);
}
/**
* 归并排序的核心逻辑，同时进行计数。
*
* @param a 待排序并计数的数组
* @param n 数组长度
* @return 不满足降序条件的数对数量
*/
private static int mergeSortAndCount(int[] a, int n) {
// 基本情况：如果数组只有一个元素，无需排序，也没有不满足条件的数对
if (n <= 1) { // 修正：n < 2 即可，n=1时返回0
return 0;
}
int mid = n / 2;
int[] l = new int[mid];
int[] r = new int[n - mid];
// 使用 System.arraycopy 提高数组复制效率
System.arraycopy(a, 0, l, 0, mid);
System.arraycopy(a, mid, r, 0, n - mid);
// 累加左右子数组的计数结果
int count = 0;
count += mergeSortAndCount(l, mid);
count += mergeSortAndCount(r, n - mid);
// 累加当前归并操作产生的计数结果
count += mergeAndCount(a, l, r);
return count;
}
/**
* 归并两个已排序的子数组，并统计不满足降序条件的数对。
* 注意：此方法将合并后的结果存回数组 a，并按照降序排列。
*
* @param a 目标数组，用于存放合并后的结果
* @param l 左子数组 (已降序排列)
* @param r 右子数组 (已降序排列)
* @return 当前归并操作中发现的不满足降序条件的数对数量
*/
private static int mergeAndCount(int[] a, int[] l, int[] r) {
// System.out.println("Merging " + Arrays.toString(l) + " and " + Arrays.toString(r)); // 可选：打印合并过程
int badPairCount = 0;
int lIdx = 0, rIdx = 0, aIdx = 0;
// 当左右子数组都还有元素时进行比较合并
while (lIdx < l.length && rIdx < r.length) {
// 如果左边元素大于等于右边元素，符合降序排列，取左边元素
if (l[lIdx] >= r[rIdx]) {
a[aIdx++] = l[lIdx++];
} else {
// 如果左边元素小于右边元素，则 r[rIdx] 比 l[lIdx] 大
// 并且 r[rIdx] 比 l 数组中从 lIdx 位置开始的所有剩余元素都大
// 这些都构成“不满足降序条件”的数对
// System.out.println(" Found bad pairs with " + r[rIdx] + " from left remaining: " + Arrays.toString(Arrays.copyOfRange(l, lIdx, l.length))); // 可选：打印详细数对
badPairCount += (l.length - lIdx); // 累加计数
a[aIdx++] = r[rIdx++]; // 取右边元素
}
}
// 将剩余的左边元素复制到目标数组
if (lIdx < l.length) {
System.arraycopy(l, lIdx, a, aIdx, l.length - lIdx);
}
// 将剩余的右边元素复制到目标数组
if (rIdx < r.length) {
System.arraycopy(r, rIdx, a, aIdx, r.length - rIdx);
}
// System.out.println(" Merged result: " + Arrays.toString(a) + ", Current bad pairs: " + badPairCount); // 可选：打印合并结果和计数
return badPairCount;
}
public static void main(String[] args) {
int[] arr1 = {7, 3, 5, 4, 1};
System.out.println("Array: " + java.util.Arrays.toString(arr1) + ", Bad pairs (Merge Sort): " + countBaadMergeSort(arr1)); // 预期输出 2
int[] arr2 = {8, 5, 6, 7, 2, 1};
System.out.println("Array: " + java.util.Arrays.toString(arr2) + ", Bad pairs (Merge Sort): " + countBaadMergeSort(arr2)); // 预期输出 3
}
}注意事项
- 累加所有子归并结果： mergeSortAndCount 函数必须累加递归调用 mergeSortAndCount(l, mid)、mergeSortAndCount(r, n - mid) 和当前 mergeAndCount 的结果，才能得到最终的总数。这是原代码中常见的错误点，只返回了最后一次合并的结果。
- 避免副作用：复制原始数组： mergeSortAndCount 方法会修改传入的数组以完成排序。如果需要保留原始数组不变，应在调用前使用 Arrays.copyOf() 创建一个副本，如 countBaadMergeSort 方法所示。
- 性能优化：使用 System.arraycopy： 在数组的复制和剩余元素的拷贝
