【Leetcode_Python】349. Intersection of Two Arrays

提供兩個陣列,找出陣列中共同的元素,再以陣列的形式輸出。

leetcode 題目在這:https://leetcode.com/problems/intersection-of-two-arrays/

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]
Explanation: [4,9] is also accepted.

Constraints:

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

以下的解答佔的空間都差不多,可是執行效率差很多,我照著執行效率做了以下的排序。

leetcode 上的四個解答可以看這裡

執行效率分別為最高到最低。

Python 解答1:

class Solution(object):
    def intersection(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        res = []
        nums1.sort()
        nums2.sort()
        i = j = 0
        while (i < len(nums1) and j < len(nums2)):
            if nums1[i] > nums2[j]:
                j += 1
            elif nums1[i] < nums2[j]:
                i += 1
            else:
                if not (len(res) and nums1[i] == res[len(res)-1]):
                    res.append(nums1[i])
                i += 1
                j += 1

        return res

我們來仔細看程式細節,先設一個空的陣列,然後用 python 內建的 sort 函式把 nums1 和 nums2 的順序排好。

res = []
nums1.sort()
nums2.sort()

然後進入迴圈判斷

while (i < len(nums1) and j < len(nums2)):
    if nums1[i] > nums2[j]:
        j += 1
    elif nums1[i] < nums2[j]:
        i += 1
    else:
        if not (len(res) and nums1[i] == res[len(res)-1]):
            res.append(nums1[i])
        i += 1
        j += 1
return res

我們用以下範例為例

[4,9,5]
[9,4,9,8,4]

先把兩個陣列進行排序。

[4,5,9]
[4,4,8,9,9]
i=0,j=0   4 = 4 ,符合第三個條件,res=[4]
i=1,j=1   5 > 4 ,符合第一個條件,j += 1,這時候 j=2
i=1,j=2   5 < 8 ,符合第二個條件,i += 1,這時候 i=2
i=2,j=2   9 > 8 ,符合第一個條件,j += 1,這時候 j=3
i=2,j=3   9 = 9,符合第三個條件,res=[4,9]

到這裡,這個程式就解釋完了。

程式中有比較不直覺的部分

if not (len(res) and nums1[i] == res[len(res)-1]):
    res.append(nums1[i])

也有其他人提出了解答,意思是如果陣列 res 為空,或者陣列 res 最後的元素不是該元素,那這就是我們要加的元素。

也可以以另一種方式表達。

""" If the result list is empty or the last thing we added wasn't this element, then it's a new element we need to add"""
if len(res) == 0 or nums1[i] != res[-1]:
     res.append(nums1[i])

Python 解答2:

這個答案很直觀,nums1 的元素中,如果 i 在 nums2的同時不在 res,就把該元素加到 res。

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        res = []
        for i in nums1:
            if i not in res and i in nums2:
                res.append(i)

        return res

Python 解答3:

class Solution(object):
    def intersection(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        res = []
        map = {}
        for i in nums1:
            map[i] = map[i]+1 if i in map else 1
        for j in nums2:
            if j in map and map[j] > 0:
                res.append(j)
                map[j] = 0

        return res

同樣以剛才的範例為例。

[4,9,5]
[9,4,9,8,4]
for i in nums1:
    map[i] = map[i]+1 if i in map else 1

nums1 中的 i 分別是 4, 9, 5。
一開始字典 map 是空的,於是 map[4]=1,map[9]=1,map[5]=1。如果重複了 map[i] 才需要+1。

for j in nums2:
    if j in map and map[j] > 0:
        res.append(j)
        map[j] = 0

nums2 中的 j 分別是 9,4,9,8,4。

如果 j 是 map 的元素之一,同時 map[j] >0。

剛才我們處理 map 的時候,map[i] 都設為 1,因此一定 >0。

之所以需要 map[j] > 0 的條件是因為,如果 j 是 map 的元素之一(程式碼中的 if j in map and map[j] > 0),就把 j append 進 res 中。

為了辨別已經 append 到 res 的元素,就把 map[j] 設為 0,這樣即使 nums2 中出現 2同樣的數字,也不會重複加入到 res 中。

Python 解答4:

這個解答雖然是最慢的,但也很直接,把陣列 nums1 和陣列 nums1 轉換為集合,再取集合的連集,就可以知道他們之間共同的元素。

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        return list(set(nums1) & set(nums2))

Leave a Comment

Your email address will not be published. Required fields are marked *