字典應用: 反轉後，兩個陣列能否相等 Make 2 Arrays Equal by Reversing LC#1460

Martijn Baudoin on Unsplash

題目敘述 Make Two Arrays Equal by Reversing Subarrays

題目給定兩個輸入陣列，請問能否透過子陣列的反轉讓兩個陣列相等?

子陣列的反轉操作次數不受限制。

如果可以，返回True

如果不行，返回False

測試範例

Example 1:

Input: target = [1,2,3,4], arr = [2,4,1,3]
Output: true
Explanation: 

反轉​ 2, 4, 1 -> 變成 1, 4, 2
arr=[1,4,2,3]

反轉 4, 2 -> 變成 2, 4
arr=[1,2,4,3]
​
反轉 4, 3-> 變成 3, 4​
arr=[1,2,3,4]
這時候達成目標，兩個陣列相等，都是[1,2,3,4]​

Example 2:

Input: target = [7], arr = [7]
Output: true
Explanation: arr is equal to target without any reverses.

Example 3:

Input: target = [3,7,9], arr = [3,7,11]
Output: false
Explanation: arr does not have value 9 and it can never be converted to target.

約束條件

Constraints:

• target.length == arr.length

兩個陣列target, arr的長度一定相同。

• 1 <= target.length <= 1000

陣列長度介於1~1000之間。

• 1 <= target[i] <= 1000

target陣列的每個元素介於1~1000之間。

• 1 <= arr[i] <= 1000

arr陣列的每個元素介於1~1000之間。

演算法 字典統計出現的數字和出現次數

因為反轉只會影響位置，所以如果要讓反轉之後的陣列有機會相同的話，必須額外滿足兩格條件:

1. 出現的數字相同，你有我也有。
2. 而且數字的出現次數也要相同，例如1都是出現兩次，5都是出現九次,....等等

用字典統計出現的數字和出現次數，如果都完全一樣，才代表兩個陣列有機會在反轉後得到相同的結果。

程式碼 字典統計出現的數字和出現次數

class Solution:
    def canBeEqual(self, target: List[int], arr: List[int]) -> bool:

        target_num_occ_dict = {}
        source_num_occ_dict = {}
        
        for num in target:
            target_num_occ_dict[num] = target_num_occ_dict.get( num, 0 ) + 1
            
        for num in arr:
            source_num_occ_dict[num] = source_num_occ_dict.get( num, 0 ) + 1
            
        return target_num_occ_dict == source_num_occ_dict

複雜度分析

時間複雜度: O(n)

線性掃描每個陣列元素，並且統計出現次數。

空間複雜度: O(n)

需要一個字典去記錄每個陣列元素的出現次數。

Reference

[1] Make Two Arrays Equal by Reversing Subarrays - LeetCode