LeetCode题练习与总结：翻转对--493

一、题目描述

给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。

你需要返回给定数组中的重要翻转对的数量。

示例 1:

输入: [1,3,2,3,1]
输出: 2

示例 2:

输入: [2,4,3,5,1]
输出: 3

注意:

1. 给定数组的长度不会超过50000。
2. 输入数组中的所有数字都在32位整数的表示范围内。

二、解题思路

这个问题可以通过归并排序的方法来解决。在归并排序的过程中，我们可以统计重要翻转对的数量。以下是解题思路：

1. 对数组进行归并排序。
2. 在归并的过程中，对于左半边的每个元素，我们需要在右半边找到第一个大于等于2倍该元素的数。
3. 找到这样的数之后，那么从右半边第一个大于等于2倍该元素的数到右半边末尾的元素都与该左半边的元素构成重要翻转对。
4. 统计这些重要翻转对的数量，并加上左右半边分别统计的重要翻转对的数量。

三、具体代码

class Solution {
    public int reversePairs(int[] nums) {
        // 辅助数组，用于归并排序
        int[] temp = new int[nums.length];
        return mergeSort(nums, 0, nums.length - 1, temp);
    }

    private int mergeSort(int[] nums, int left, int right, int[] temp) {
        if (left >= right) {
            return 0;
        }
        int mid = left + (right - left) / 2;
        int count = mergeSort(nums, left, mid, temp) + mergeSort(nums, mid + 1, right, temp);
        // 统计重要翻转对的数量
        count += merge(nums, left, mid, right, temp);
        return count;
    }

    private int merge(int[] nums, int left, int mid, int right, int[] temp) {
        int count = 0;
        int j = mid + 1;
        // 统计重要翻转对
        for (int i = left; i <= mid; i++) {
            while (j <= right && (long)nums[i] > 2L * nums[j]) {
                j++;
            }
            count += j - (mid + 1);
        }
        // 归并排序的合并步骤
        System.arraycopy(nums, left, temp, left, right - left + 1);
        int i = left, k = left;
        j = mid + 1;
        while (i <= mid && j <= right) {
            if (temp[i] <= temp[j]) {
                nums[k++] = temp[i++];
            } else {
                nums[k++] = temp[j++];
            }
        }
        while (i <= mid) {
            nums[k++] = temp[i++];
        }
        while (j <= right) {
            nums[k++] = temp[j++];
        }
        return count;
    }
}

在这段代码中，mergeSort 函数用于递归地对数组进行归并排序，并在归并过程中调用 merge 函数来统计重要翻转对的数量。merge 函数除了执行归并操作外，还负责计算当前区间内的翻转对数量。这里使用了一个小技巧，即通过计算右半边第一个大于等于2倍左半边元素的索引来计算翻转对的数量。注意，在比较时使用了 long 类型来避免整数溢出。

四、时间复杂度和空间复杂度

1. 时间复杂度

• 归并排序的过程将数组分成两半，每次递归调用都会处理数组的一半大小，因此递归的深度是 O(logN)，其中 N 是数组的长度。
• 在每一层递归中，我们需要对两个子数组进行合并，合并过程中需要遍历两个子数组的所有元素，这一步的时间复杂度是 O(N)。
• 在合并过程中，我们还需要统计重要翻转对的数量。对于左子数组的每个元素，我们可能需要遍历右子数组来找到第一个大于等于2倍该元素的数，这一步的时间复杂度在最坏情况下是 O(N)。
• 综合上述步骤，每层递归的时间复杂度是 O(N) + O(N) = O(N)，递归深度是 O(logN)，因此总的时间复杂度是 O(NlogN)。

2. 空间复杂度

• 归并排序需要一个与原数组相同大小的辅助数组来存储合并过程中的临时结果，因此空间复杂度是 O(N)。
• 递归调用栈的深度是 O(logN)，因为每次递归都是处理数组的一半大小。
• 综合上述步骤，总的空间复杂度是 O(N) + O(logN)，即 O(N)，因为 O(logN) 相对于 O(N) 可以忽略不计。

五、总结知识点

• 归并排序（Merge Sort）：

  • 归并排序是一种分治策略的排序算法，它将数组分成两半，分别对两半进行排序，然后将排序好的两半合并。
  • 归并排序的时间复杂度通常是 O(NlogN)，空间复杂度是 O(N)。

• 递归（Recursion）：

  • 递归是一种编程技巧，函数调用自身来解决问题。
  • 在归并排序中，递归用于将问题分解成更小的子问题。

• 辅助数组：

  • 辅助数组用于在合并过程中临时存储数组元素，避免覆盖原数组中的数据。

• System.arraycopy 方法：

  • 这是一个Java标准库中的方法，用于高效地复制数组的一部分到另一个位置。

• 整数溢出（Integer Overflow）：

  • 在比较两个整数相乘时，如果直接使用 int 类型可能会导致溢出。
  • 使用 long 类型来避免在比较 (long)nums[i] > 2L * nums[j] 时发生整数溢出。

• 二分查找（Binary Search）：

  • 在统计重要翻转对的过程中，实际上是通过遍历左子数组，并在右子数组中找到一个合适的位置，这个过程类似于二分查找，但这里是线性查找。

• 计数逻辑：

  • 对于左子数组的每个元素，通过线性查找确定其在右子数组中第一个大于等于2倍该元素的索引，然后通过计算索引差来统计翻转对的数量。

• 合并过程：

  • 合并过程是将两个已排序的子数组合并成一个有序的数组，这是归并排序中的关键步骤。

• 算法设计：

  • 代码展示了如何在排序算法中嵌入额外的逻辑（统计翻转对）而不影响排序本身。

• 边界条件处理：

  • 递归的终止条件是 if (left >= right)，这确保了递归能够正确地结束。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。