引言：理解“坏对”问题
在数组处理中，有时我们需要识别不符合特定排序规则的元素对。本教程关注的是一种特殊的“坏对”：给定一个整数数组 hs，如果存在索引 i < j 使得 hs[i] < hs[j]，则 (hs[i], hs[j]) 被视为一个“坏对”。我们的目标是统计数组中所有此类“坏对”的总数。
例如：
- 对于 hs = [7, 3, 5, 4, 1]，坏对有 (3, 5) 和 (3, 4)，总数为 2。
- 对于 hs = [8, 5, 6, 7, 2, 1]，坏对有 (5, 6)、(5, 7) 和 (6, 7)，总数为 3。
这个问题本质上是统计数组中的“逆序对”，但通常逆序对定义为 arr[i] > arr[j] 且 i < j。这里我们是统计 arr[i] < arr[j] 且 i < j 的对，可以理解为在目标是降序排列时，元素顺序错误的对。
暴力解法：O(N^2) 时间复杂度
最直观的方法是使用两层嵌套循环遍历数组，对每对满足 i < j 的元素进行比较。
算法思路
- 初始化一个计数器 count 为 0。
- 外层循环 i 从 0 遍历到 hs.length - 1。
- 内层循环 j 从 i + 1 遍历到 hs.length - 1。
- 在内层循环中，如果 hs[i] < hs[j]，则 count 加 1。
- 返回 count。
示例代码
public class BadPairCounter {
/**
* 使用暴力法统计数组中的“坏对”数量。
* 时间复杂度：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++) {
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 (Brute Force): " + countBaadBruteForce(arr1)); // Expected: 2
int[] arr2 = {8, 5, 6, 7, 2, 1};
System.out.println("Array: " + java.util.Arrays.toString(arr2) + ", Bad pairs (Brute Force): " + countBaadBruteForce(arr2)); // Expected: 3
}
}局限性
暴力解法简单易懂，但其时间复杂度为 O(N^2)，对于大型数据集，性能会急剧下降，导致计算时间过长。
归并排序优化法：O(N log N) 时间复杂度
为了提高效率，我们可以利用归并排序（Merge Sort）的特性来解决这个问题。归并排序在合并两个已排序的子数组时，会进行元素间的比较，这正是我们统计“坏对”的绝佳时机。
核心思想
标准的归并排序将数组递归地分成两半，直到每个子数组只包含一个元素。然后，它将这些子数组两两合并，每次合并都确保子数组是有序的。在这个合并过程中，我们可以有效地统计“坏对”。
为了统计 hs[i] < hs[j] 且 i < j 的对，我们可以修改归并排序，使其在合并两个降序排列的子数组时进行计数。
假设我们有两个已经按降序排列的子数组 L 和 R。在合并它们时，我们从 L 和 R 的头部开始比较：
- 如果 L[lIdx] >= R[rIdx]，这意味着 L[lIdx] 已经比 R[rIdx] 大或相等，符合降序要求，我们将其放入结果数组。
- 如果 L[lIdx] < R[rIdx]，这意味着 L[lIdx] 小于 R[rIdx]。由于 L 和 R 都是降序排列的，并且 L[lIdx] 是 L 中当前最小（即最靠后）的未处理元素，那么 L[lIdx] 不仅小于 R[rIdx]，它也小于 R 中所有比 R[rIdx] 更小的元素。更重要的是，R[rIdx] 比 L 中所有从 L[lIdx] 到 L 结尾的元素都大。因此，R[rIdx] 与 L 中所有剩余的元素（L[lIdx] 到 L[L.length-1]）都构成了“坏对”。此时，我们将 R[rIdx] 放入结果数组，并将 count 增加 L 中剩余元素的数量 (L.length - lIdx)。
算法步骤
- countBaad 方法：作为入口，调用 mergeSort 方法。为了避免修改原始数组，可以先复制一份。
-
mergeSort 方法：
- 基准情况：如果数组长度小于 2（即 0 或 1），则无需排序，也没有“坏对”，返回 0。
- 分割：将数组 a 分成左右两个子数组 l 和 r。可以使用 System.arraycopy 提高效率。
- 递归：递归调用 mergeSort(l, mid) 和 mergeSort(r, n - mid)，并将它们返回的“坏对”数量累加到 result 中。
- 合并与计数：调用 merge(a, l, r) 方法，将左右子数组合并到 a 中，并返回合并过程中发现的“坏对”数量，同样累加到 result 中。
- 返回 result。
-
merge 方法：
- 初始化 size（用于计数坏对）、lIdx、rIdx、aIdx 为 0。
- 当 lIdx 和 rIdx 都在各自数组范围内时：
- 如果 l[lIdx] >= r[rIdx]：将 l[lIdx] 放入 a，lIdx 和 aIdx 递增。
- 如果 l[lIdx] < r[rIdx]：这意味着 l[lIdx] 与 r[rIdx] 及其后面所有比 l[lIdx] 大的元素形成“坏对”。更准确地说，r[rIdx] 比 L 中所有从 lIdx 到 L.length-1 的元素都大。因此，将 L 中剩余的元素数量 (l.length - lIdx) 加到 size 中。然后将 r[rIdx] 放入 a，rIdx 和 aIdx 递增。
- 处理剩余元素：将 l 或 r 中剩余的元素直接复制到 a 的末尾。这里同样可以使用 System.arraycopy。
- 返回 size。
示例代码
import java.util.Arrays;
public class BadPairMergeSortCounter {
/**
* 入口方法，统计数组中的“坏对”数量。
* 为了不修改原始数组，先进行复制。
*
* @param hs 输入整数数组
* @return 坏对的总数
*/
public static int countBaad(int[] hs) {
// 复制数组以避免修改原始输入
int[] tempArray = Arrays.copyOf(hs, hs.length);
return mergeSort(tempArray, tempArray.length);
}
/**
* 递归地对数组进行归并排序并统计“坏对”。
*
* @param a 待排序和计数的数组
* @param n 数组长度
* @return 当前子数组及其子问题中发现的坏对总数
*/
public static int mergeSort(int[] a, int n) {
if (n <= 1) { // 基准情况：数组长度为0或1，没有坏对
return 0;
}
int mid = n / 2;
int[] l = new int[mid];
int[] r = new int[n - mid];
// 分割数组
System.arraycopy(a, 0, l, 0, mid);
if (n - mid > 0) { // 确保右子数组有元素
System.arraycopy(a, mid, r, 0, n - mid);
}
int result = 0;
// 递归统计左右子数组中的坏对
result += mergeSort(l, mid);
result += mergeSort(r, n - mid);
// 合并左右子数组，并统计合并过程中产生的坏对
result += merge(a, l, r);
return result;
}
/**
* 合并两个已降序排序的子数组，并统计合并过程中产生的“坏对”。
*
* @param a 目标数组，用于存放合并后的结果
* @param l 左子数组 (已降序排序)
* @param r 右子数组 (已降序排序)
* @return 合并过程中发现的坏对数量
*/
public static int merge(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 {
// 如果左边元素小于右边元素 (l[lIdx] < r[rIdx])
// 这意味着 l[lIdx] 与 r[rIdx] 构成一个“坏对”。
// 由于 l 数组和 r 数组都是降序排列的，
// r[rIdx] 比 l 数组中从 lIdx 位置到末尾的所有元素都大。
// 因此，r[rIdx] 与 l 数组中所有剩余元素 (l.length - lIdx 个) 都构成“坏对”。
badPairCount += (l.length - lIdx);
// System.out.println(" Found " + (l.length - lIdx) + " bad pairs with " + r[rIdx] + " from " + Arrays.toString(Arrays.copyOfRange(l, lIdx, l.length))); // 可选：详细日志
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);
}
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): " + countBaad(arr1)); // Expected: 2
int[] arr2 = {8, 5, 6, 7, 2, 1};
System.out.println("Array: " + java.util.Arrays.toString(arr2) + ", Bad pairs (Merge Sort): " + countBaad(arr2)); // Expected: 3
}
}性能与注意事项
- 时间复杂度：归并排序本身的时间复杂度为 O(N log N)。在 merge 过程中，我们只增加了常数时间的比较和计数操作，因此整体时间复杂度依然保持在 O(N log N)，这比暴力解法 O(N^2) 有显著提升。
- 空间复杂度：归并排序需要额外的空间来存储子数组，因此空间复杂度为 O(N)。
- 避免副作用：mergeSort 算法会对其操作的数组进行排序。如果仅仅需要统计“坏对”数量而不希望修改原始数组，务必在 countBaad 方法中对输入数组进行深拷贝，例如使用 Arrays.copyOf(hs, hs.length)。
- System.arraycopy：在复制子数组时，使用 System.arraycopy 比手动循环赋值效率更高，尤其对于大型数组。
总结
统计数组中特定类型的“坏对”是一个常见的算法问题。虽然暴力解法简单直接，但其 O(N^2) 的时间复杂度使其不适用于大规模数据。通过巧妙地修改归并排序算法，我们可以在 O(N log N) 的时间复杂度内高效地解决这个问题，这在处理大量数据时具有显著的性能优势。理解归并排序中 merge 阶段的计数逻辑是实现这一优化的关键。在实际应用中，还需注意对原始数据的保护（通过复制数组）以及使用高效的数组操作（如 System.arraycopy）。
