【劍指offer：數組中的逆序對】暴力法、歸并排序（JavaScript實作）

題目描述：給定一個字元串，請你找出其中不含有重複字元的 最長子串 的長度。

解法 1: 暴力法（TLE）

直接雙重循環，挨個檢查是否為逆序對。代碼實作比較簡單：

/**
 * @param {number[]} nums
 * @return {number}
 */
var reversePairs = function(nums) {
    let res = 0;
    const length = nums.length;
    for (let i = 0; i < length; ++i) {
        for (let j = i + 1; j < length; ++j) {
            nums[i] > nums[j] && ++res;
        }
    }

    return res;
};           

複制

時間複雜度是$O(N^2)$。在 leetcode 上會 TLE，無法通過（畢竟這是道标注「困難」的題目）。

解法 2: 歸并排序（正确解法）

這題的正确解法是要借助歸并排序的思路，在歸并的過程中，快速統計逆序對。這種解法比較難想到，但是應用歸并排序的題目真的不多，是以這題很有研究和收藏意義。

核心的解決邏輯都封裝在 findInversePairNum 函數中。它的職能就是統計數組

arr[start, end]

範圍中的逆序對，并且統計完後，

arr[start, end]

範圍中的元素會被排序（這點和歸并排序的過程一樣）。

那麼函數又是如何快速統計逆序對的呢？大體過程如下：

• 遞歸調用，拿到左子數組和右子數組的逆序對（此時，左子數組和右子數組也都排序完成了）
• 指針 i 和 j 分别指向左子數組和右子數組的最右側，此時會有 2 種情況：

  • arr[i] > arr[j]

    ：那麼說明

    arr[i]

    大于右子數組中所有元素，逆序對增加

    j - start - length

    ，向左邊移動指針 i

  • arr[i] <= arr[j]

    : 對

    arr[i]

    來說，不存在逆序對，向左邊移動指針 j
• i 和 j 周遊完各自數組後，最後傳回逆序對之和即可

代碼實作如下：

// ac位址：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
// 原文位址：https://xxoo521.com/2020-03-12-reverse-pairs/
/**
 * @param {number[]} nums
 * @return {number}
 */
var reversePairs = function(nums) {
    return findInversePairNum(nums, 0, nums.length - 1);
};

/**
 * @param {number[]} arr
 * @param {number} start
 * @param {number} end
 */
function findInversePairNum(arr, start, end) {
    if (start >= end) return 0;

    const copy = new Array(end - start + 1);
    const length = Math.floor((end - start) / 2); // 左數組長度
    const leftNum = findInversePairNum(arr, start, start + length);
    const rightNum = findInversePairNum(arr, start + length + 1, end);

    let i = start + length;
    let j = end;
    let copyIndex = end - start;
    let num = 0;
    while (i >= start && j >= start + length + 1) {
        if (arr[i] > arr[j]) {
            num += j - start - length;
            copy[copyIndex--] = arr[i--];
        } else {
            copy[copyIndex--] = arr[j--];
        }
    }

    while (i >= start) {
        copy[copyIndex--] = arr[i--];
    }

    while (j >= start + length + 1) {
        copy[copyIndex--] = arr[j--];
    }

    for (let k = start; k <= end; ++k) {
        arr[k] = copy[k - start];
    }

    return num + leftNum + rightNum;
}           

複制

時間複雜度是$O(NlogN)$，空間複雜度是$O(N)$。如果還是覺得不好了解，可以以數組 7、5、6、4 為例，按照前面過程，手動計算一下。