🔗 🟢 1122. Relative Sort Array 1189

tags: `Weekly Contest 145` `陣列(Array)` `排序(Sorting)` `計數排序(Counting Sort)` `雜湊表(Hash Table)`

題意

給定兩個整數陣列 $arr1$ 和 $arr2$ ，其中 $arr2$ 中的元素是唯一的，且 $arr2$ 中的每個元素都出現在 $arr1$ 中。

對 $arr1$ 中的元素進行排序，使得 $arr1$ 中的元素相對順序與 $arr2$ 中的相對順序相同。不在 $arr2$ 中的元素需要按升序排列並放在 $arr1$ 的末尾。

約束條件

$1 \leq \text{arr1.length}, \text{arr2.length} \leq 1000$
$0 \leq \text{arr1}[i], \text{arr2}[i] \leq 1000$
$arr2$ 中的所有元素都是唯一的。
每個 $arr2[i]$ 都在 $arr1$ 中。

思路

方法一：自訂排序

由於需要按照特定的順序對 $arr1$ 進行排序，因此我們可以通過自訂排序來實現這個需求。

為了按照 $arr2$ 中的相對順序對 $arr1$ 進行排序，因此我們需要建立一個雜湊表(Hash Table) ，將 $arr2$ 中的每個元素映射到其在 $arr2$ 中的索引。來記錄 $arr2$ 中每個元素的排名。這樣，我們可以很方便地知道 $arr1$ 中的元素在 $arr2$ 中的相對順序。

而在排序時，我們可以根據這個映射來對 $arr1$ 進行排序，具體步驟如下：

在比較 $a$ 和 $b$ 時，如果 $a$ 和 $b$ 都在 $arr2$ 中，我們根據它們在 $arr2$ 中的排名來比較。
如果 $a$ 和 $b$ 都不在 $arr2$ 中，我們按照自然順序來比較。
如果 $a$ 在 $arr2$ 中而 $b$ 不在，我們將 $a$ 放在 $b$ 前面。

除了上述方式外，也能將不在 $arr2$ 中的元素 $x$ 的排名視為 $1000 + x$ ，這樣就能夠保證不在 $arr2$ 中的元素會按照升序排列。

複雜度分析

時間複雜度： $\mathcal{O}(n + m \log m)$ $O (n + m lo g m)$ ，其中 $n$ $n$ 是 $arr2$ $a rr 2$ 的長度， $m$ $m$ 是 $arr1$ $a rr 1$ 的長度。
- 建立排名映射需要 $\mathcal{O}(n)$ 的時間。
- 排序的時間複雜度是 $\mathcal{O}(m \log m)$ 。
空間複雜度： $\mathcal{O}(n)$ ，使用了額外的映射來存儲 $arr2$ 的排名。

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        rank = {x: i for i, x in enumerate(arr2)}
        return sorted(arr1, key=lambda x: rank.get(x, 1000 + x))

class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        unordered_map<int, int> rank;
        for (int i = 0; i < arr2.size(); i++) rank[arr2[i]] = i;
        sort(arr1.begin(), arr1.end(), [&](int x, int y) {
            if (rank.count(x)) {
                return rank.count(y) ? rank[x] < rank[y] : true;
            } else {
                return rank.count(y) ? false : x < y;
            }
        });
        return arr1;
    }
};

方法二：計數排序(Counting Sort)

注意到約束條件中的數字範圍是 $0 \leq \text{arr1}[i], \text{arr2}[i] \leq 1000$ ，因此我們可以基於值域，使用計數排序(Counting Sort) 的思想來解決問題。

首先紀錄 $arr1$ 中每個元素的出現次數，然後根據 $arr2$ 的順序重建陣列，最後將 $arr2$ 中未出現的元素按升序排列加入結果陣列即可。此外，也能透過直接修改 $arr1$ 來達到相同的效果。

具體步驟如下：

遍歷 $arr1$ ，並使用一個長度為 $1001$ 的計數陣列 $cnt 來計算 $arr1$ 中每個元素的出現次數。
遍歷 $arr2$ ，根據 $cnt$ 中的計數，將 $arr2$ 中的元素按照其在 $arr2$ 中的順序加入到結果陣列 $ans$ 中，並將這些元素的計數歸零。
最後，對於那些不在 $arr2$ 中但在 $arr1$ 中出現的元素，按照自然數升序的順序，將它們加入結果陣列 $ans$ 中。

複雜度分析

時間複雜度： $\mathcal{O}(n + m + k)$ $O (n + m + k)$ ，其中 $n$ $n$ 是 $arr1$ $a rr 1$ 的長度， $m$ $m$ 是 $arr2$ $a rr 2$ 的長度， $k$ $k$ 是數字範圍的大小，本題中為 1001。
- 對 $arr1$ 中的元素進行計數需要 $\mathcal{O}(n)$ 時間。
- 對 $arr2$ 中的元素進行處理需要 $\mathcal{O}(m)$ 時間。
- 最後處理剩餘元素的步驟需要 $\mathcal{O}(k)$ 時間。
空間複雜度： $\mathcal{O}(k)$ ，需要一個大小為 $1001$ 的計數陣列 $cnt$ 。

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        cnt = [0] * (1001)
        for x in arr1:
            cnt[x] += 1
        
        ans = []
        for x in arr2:
            ans.extend([x] * cnt[x])
            cnt[x] = 0
        for x in range(1001):
            if cnt[x] > 0:
                ans.extend([x] * cnt[x])
        return ans

class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        vector<int> cnt(1001);
        for (int x : arr1) cnt[x]++;
        int i = 0;
        for (int x : arr2)
            while (cnt[x]-- > 0)
                arr1[i++] = x;
        for (int x = 0; x < 1001; x++)
            while (cnt[x]-- > 0)
                arr1[i++] = x;
        return arr1;
    }
};