LeetCode: 2215-Find the Difference of Two Arrays 解題紀錄

題目

Given two 0-indexed integer arrays nums1 and nums2, return a list answer of size 2 where:

• answer[0] is a list of all distinct integers in nums1 which are not present in nums2.
• answer[1] is a list of all distinct integers in nums2 which are not present in nums1.

Note that the integers in the lists may be returned in any order.

Example 1:

Input: nums1 = [1,2,3], nums2 = [2,4,6]
Output: [[1,3],[4,6]]
Explanation:
For nums1, nums1[1] = 2 is present at index 0 of nums2, whereas nums1[0] = 1 and nums1[2] = 3 are not present in nums2. Therefore, answer[0] = [1,3].
For nums2, nums2[0] = 2 is present at index 1 of nums1, whereas nums2[1] = 4 and nums2[2] = 6 are not present in nums2. Therefore, answer[1] = [4,6].

Example 2:

Input: nums1 = [1,2,3,3], nums2 = [1,1,2,2]
Output: [[3],[]]
Explanation:
For nums1, nums1[2] and nums1[3] are not present in nums2. Since nums1[2] == nums1[3], their value is only included once and answer[0] = [3].
Every integer in nums2 is present in nums1. Therefore, answer[1] = [].

Constraints:

• 1 <= nums1.length, nums2.length <= 1000
• -1000 <= nums1[i], nums2[i] <= 1000

題目給定兩個正整數的陣列，我們需要找出兩個陣列中不重複的元素，並把 nums1 的元素當做返回陣列的第一個陣列中值、nums2 的元素當做返回陣列的第二個陣列中值。

---

解題思路

Brute Force

首先，自然會想要使用暴力法來解解看，順便看一下效果多差。

1. 首先，將兩個陣列排序
2. 將兩個陣列去重複
3. 接著用雙層 for 迴圈，窮舉出兩陣列重複的值
4. 將不重複的值分別填入回傳陣列的第一個元素和第二個元素

Brute Force 複雜度

Time Complexity	O(n^2)
Space Complexity	O(n)

雖然看起來是 O(n^2)，但時間上中間還跑過一次 O(nxlog(n))，這個方法是真的很慢呢。

C++ 範例程式碼

class Solution {
public:
    vector<vector<int>> findDifference(vector<int>& nums1, vector<int>& nums2) {
        // Init
        vector<int> duplicated;
        vector<vector<int>> results(2, vector<int>{});

        // Sort
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());

        // Drop duplicated
        nums1.erase(unique(nums1.begin(), nums1.end()), nums1.end());
        nums2.erase(unique(nums2.begin(), nums2.end()), nums2.end());

        // Find difference
        for (int i=0; i<nums1.size(); ++i) {
            for (int j=0; j<nums2.size(); ++j) {
                if (nums1[i] == nums2[j]) {
                    duplicated.emplace_back(nums1[i]);
                    break;
                }
            }
        }

        for (int i=0; i<nums1.size(); ++i) {
            if (find(duplicated.begin(), duplicated.end(), nums1[i]) == duplicated.end()) {
                results[0].emplace_back(nums1[i]);
            }
        }

        for (int i=0; i<nums2.size(); ++i) {
            if (find(duplicated.begin(), duplicated.end(), nums2[i]) == duplicated.end()) {
                results[1].emplace_back(nums2[i]);
            }
        }

        return results;
    }
};

Python 範例程式碼

class Solution:
    def findDifference(self, nums1: List[int], nums2: List[int]) -> List[List[int]]:
        # Init
        duplicated = []
        results = [[], []]

        # Sort
        sorted(nums1)
        sorted(nums2)

        # Drop duplicated
        nums1 = set(nums1)
        nums2 = set(nums2)

        # Find difference
        for n1 in nums1:
            for n2 in nums2:
                if n1 == n2:
                    duplicated.append(n1)
                    break

        # Fill `results`
        for n1 in nums1:
            if n1 not in duplicated:
                results[0].append(n1)

        for n2 in nums2:
            if n2 not in duplicated:
                results[1].append(n2)

        return results

Unordered Set 結構

若是善用 set 資料結構的話，則能大幅提升效果。同樣，這在 C++ 感覺比較明顯。

Unordered Set 結構複雜度

Time Complexity	O(n)
Space Complexity	O(n)

C++ 範例程式碼

class Solution {
public:
    vector<vector<int>> findDifference(vector<int>& nums1, vector<int>& nums2) {
        // Init
        unordered_set<int> count1(nums1.begin(), nums1.end());
        unordered_set<int> count2(nums2.begin(), nums2.end());
        vector<vector<int>> results(2, vector<int>());

        // Fill in `results`
        for (auto& num: count1) {
            if (!count2.count(num)) {
                results[0].emplace_back(num);
            }
        }
        for (auto& num: count2) {
            if (!count1.count(num)) {
                results[1].emplace_back(num);
            }
        }

        return results;
    }
};

Python 範例程式碼

class Solution:
    def findDifference(self, nums1: List[int], nums2: List[int]) -> List[List[int]]:
        # Init
        duplicated = []
        results = [[], []]

        # Drop duplicated
        nums1 = set(nums1)
        nums2 = set(nums2)

        # Fill `results`
        for n1 in nums1:
            if n1 not in nums2:
                results[0].append(n1)

        for n2 in nums2:
            if n2 not in nums1:
                results[1].append(n2)

        return results

---

References

• 2215. Find the Difference of Two Arrays

---

Read More

• LeetCode 解題紀錄目錄