題目資訊

題目編號: 2179
題目連結: Count Good Triplets in an Array
主題: Array, Binary Search, Divide and Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set

題目敘述

你有兩個以0作為索引的數組 nums1 和 nums2，長度均為 $n$，且皆為 $[0, 1, \ldots, n - 1]$ 的排列。

一個好的三元組是由 3 個不同的值組成，且這些值在 nums1 和 nums2 中的位置均以遞增順序排列。換句話說，如果我們考慮 $pos1_v$ 為值 $v$ 在 nums1 中的索引，$pos2_v$ 為值 $v$ 在 nums2 中的索引，那麼一個好的三元組將會是集合 $(x, y, z)$，其中 $0 \leq x, y, z \leq n - 1$，滿足 $pos1_x < pos1_y < pos1_z$ 且 $pos2_x < pos2_y < pos2_z$。

返回好的三元組的總數。

範例 1:

輸入: nums1 = [2,0,1,3], nums2 = [0,1,2,3]
輸出: 1
解釋: 
有 4 個三元組 (x,y,z) 滿足 $pos1_x < pos1_y < pos1_z$。它們是 (2,0,1), (2,0,3), (2,1,3) 和 (0,1,3)。 
在這些三元組中，只有三元組 (0,1,3) 滿足 $pos2_x < pos2_y < pos2_z$。因此，只有 1 個好的三元組。

範例 2:

輸入: nums1 = [4,0,1,3,2], nums2 = [4,1,0,2,3]
輸出: 4
解釋: 4 個好的三元組是 (4,0,3), (4,0,2), (4,1,3) 和 (4,1,2)。

約束條件:

$n == nums1.length == nums2.length$
$3 \leq n \leq 10^5$
$0 \leq nums1[i], nums2[i] \leq n - 1$
nums1 和 nums2 是 $[0, 1, \ldots, n - 1]$ 的排列。

直覺

這個問題要求我們在兩個序列的排列中找到「好三元組」的數量。一個好三元組由三個元素組成，它們在兩個排列中以特定的遞增順序出現。由於 nums1 和 nums2 是同一集合的排列，我們可以利用此特性來有效地追蹤相對位置，使我們能夠識別有效的三元組，而無需直接以 $O(n^3)$ 的方式進行比較。

解法

這個解決方案利用了一種稱為費威克樹（或二元索引樹）的數據結構，該數據結構在查詢數組的前綴和以及執行點更新時具有對數時間的效率。這特別適合用於計算反轉數或在我們的情況下計數有效的三元組配置。

位置映射：
首先，創建一個映射 nums2 中元素位置的映射，存儲在數組 pos2 中，其中 pos2[val] 給出 val 在 nums2 中的位置。此映射有助於從 nums1 的順序轉換到 nums2 的順序。
從 nums1 到 nums2 的索引映射：
使用 pos2 映射，將 nums1 中的元素轉換為它們在 nums2 中的相應索引，形成 indexMapping。此處，indexMapping[i] 給出元素 nums1[i] 在 nums2 中的位置。
費威克樹初始化：
初始化一個費威克樹以有效地追蹤前綴和。此結構支持對數時間的更新和前綴查詢。
計數好三元組：
遍歷 indexMapping 中的每個位置，將此視為潛在三元組的中間元素 mid：
- 計算 left：該元素之前所有索引中的較小值數量，可使用費威克樹中到 indexMapping[mid] 的前綴和查詢得到。
- 計算 right：潛在的較大值位於當前 mid 右側，由右側剩餘索引數減去計入 left 中的數量得到。
- 更新費威克樹以包括當前位置。
- 可以在當前 mid 處結束的好三元組數量通過乘以 left 和 right 獲得，因為這些是獨立的選擇。
複雜度考量：
在費威克樹中的每次更新和查詢操作都是 $O(\log n)$，並且整體方法涉及一次遍歷數組，因此複雜度大約為 $O(n \log n)$。在問題給定的限制下，這是有效的。

通過遵循這些步驟，該算法有效地計算好三元組的數量，並遵從問題聲明中指定的條件。

程式碼

C++

class FenwickTree {
private:
    vector<int> tree;

    // 返回數字的最低位 (1)
    int lowbit(int num) { 
        return num & -num; 
    }

public:
    // 初始化給定大小的 Fenwick Tree
    FenwickTree(int size) { 
        tree = vector(size + 1, 0); 
    }

    // 在特定索引處以一個增量值更新 Fenwick Tree
    void update(int idx, int delta) {
        idx++;
        while (idx < tree.size()) {
            tree[idx] += delta;
            idx += lowbit(idx);
        }
    }

    // 查詢 Fenwick Tree 中到給定索引的前綴和
    int query(int idx) {
        idx++;
        int sum = 0;
        while (idx > 0) {
            sum += tree[idx];
            idx -= lowbit(idx);
        }
        return sum;
    }
};

class Solution {
public:
    long long goodTriplets(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        long long totalGoodTriplets = 0;
        vector<int> pos2(n), indexMapping(n);

        // 記錄每個元素在 nums2 中的位置
        for (int i = 0; i < n; i++) {
            pos2[nums2[i]] = i;
        }

        // 映射 nums1 元素在 nums2 中的位置
        for (int i = 0; i < n; i++) {
            indexMapping[i] = pos2[nums1[i]];
        }

        FenwickTree tree(n);

        // 計算好三元組
        for (int mid = 0; mid < n; mid++) {
            int pos = indexMapping[mid];
            int left = tree.query(pos);
            int right = (n - pos - 1) - (mid - left);

            // 更新 Fenwick Tree 目前的中間位置
            tree.update(pos, 1);

            // 根據目前的 left 和 right 值計算好三元組的數量
            totalGoodTriplets += static_cast<long long>(left) * right;
        }

        return totalGoodTriplets;
    }
};

Python

class FenwickTree:
    def __init__(self, size):
        # 初始化Fenwick Tree並設定大小
        self.tree = [0] * (size + 1)

    def lowbit(self, num):
        # 返回數字的最低位元 (1)
        return num & -num

    def update(self, idx, delta):
        # 在Fenwick Tree的特定索引位置進行更新，增加一個增量值
        idx += 1
        while idx < len(self.tree):
            self.tree[idx] += delta
            idx += self.lowbit(idx)

    def query(self, idx):
        # 查詢Fenwick Tree中至給定索引位置的前綴和
        idx += 1
        sum = 0
        while idx > 0:
            sum += self.tree[idx]
            idx -= self.lowbit(idx)
        return sum

class Solution:
    def goodTriplets(self, nums1, nums2):
        n = len(nums1)
        totalGoodTriplets = 0
        pos2 = [0] * n
        indexMapping = [0] * n

        # 記錄nums2中每個元素的位置
        for i in range(n):
            pos2[nums2[i]] = i

        # 映射nums1元素在nums2中的位置
        for i in range(n):
            indexMapping[i] = pos2[nums1[i]]

        tree = FenwickTree(n)

        # 計算良好三元組
        for mid in range(n):
            pos = indexMapping[mid]
            left = tree.query(pos)
            right = (n - pos - 1) - (mid - left)

            # 更新當前中間位置的Fenwick Tree
            tree.update(pos, 1)

            # 根據當前left和right值計算良好三元組的數量
            totalGoodTriplets += left * right

        return totalGoodTriplets

複雜度分析

時間複雜度: $O(n \log n)$
該演算法主要由三個組成部分決定其時間複雜度：
1. 初始設置： 填充 pos2 和 indexMapping 陣列需要 $O(n)$ 的時間，這裡 $n$ 是 nums1（或 nums2）的長度。
2. Fenwick 樹的更新和查詢： 主迴圈遍歷 indexMapping 中的每個元素，在每次迭代中，它在 Fenwick 樹上執行一次查詢和更新操作。Fenwick 樹上的更新和查詢操作都需要 $O(\log n)$ 的時間。由於這個迴圈運行 $n$ 次，這部分的總時間複雜度是 $O(n \log n)$。
綜合這些組件，由於 Fenwick 樹操作支配，主導項為 $O(n \log n)$，因此總體時間複雜度是 $O(n \log n)$。
空間複雜度: $O(n)$
空間複雜度主要由以下額外的存儲空間決定：
1. Fenwick 樹存儲： Fenwick 樹本身維護一個大小為 $n+1$ 的 tree 陣列。
2. 輔助陣列： 兩個輔助陣列 pos2 和 indexMapping 的大小都是 $n$。
因此，總的空間複雜度是 $O(n)$，因為 Fenwick 樹和輔助陣列的大小主導了空間的使用。

CS Note
En

Leetcode 2179. Count Good Triplets in an Array

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析