題目

難度：★★☆☆☆
類型：數(shù)組

給定兩個(gè)數(shù)組，編寫一個(gè)函數(shù)來計(jì)算它們的交集。

說明：
輸出結(jié)果中每個(gè)元素出現(xiàn)的次數(shù)，應(yīng)與元素在兩個(gè)數(shù)組中出現(xiàn)的次數(shù)一致。
我們可以不考慮輸出結(jié)果的順序。

進(jìn)階:
如果給定的數(shù)組已經(jīng)排好序呢？你將如何優(yōu)化你的算法？
如果 nums1 的大小比 nums2 小很多，哪種方法更優(yōu)？
如果 nums2 的元素存儲(chǔ)在磁盤上，磁盤內(nèi)存是有限的，并且你不能一次加載所有的元素到內(nèi)存中，你該怎么辦？

示例

示例 1:
輸入: nums1 = [1,2,2,1], nums2 = [2,2]
輸出: [2,2]

示例 2:
輸入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出: [4,9]

解答

這道題與【題目349. 兩個(gè)數(shù)的交集】唯一的不同，就是結(jié)果中數(shù)值相同的元素可以重復(fù)出現(xiàn)。

方案1：交集定義

我們可以遍歷其中一個(gè)數(shù)組，如果當(dāng)前數(shù)字在另一個(gè)數(shù)組中出現(xiàn)，則記錄下當(dāng)前結(jié)果的同時(shí)，刪除另一個(gè)數(shù)組中的該元素，遍歷完成即可實(shí)現(xiàn)題目所描述的求取交集的任務(wù)。

class Solution(object):
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        r = []                      # 結(jié)果列表
        tmp = nums2[:]              # 準(zhǔn)備一個(gè)臨時(shí)變量，復(fù)制nums2，為了防止對(duì)nums2的修改
        for num in nums1:           # 遍歷nums1中的每一個(gè)變量num
            if num in tmp:          # 如果當(dāng)前元素num在另一個(gè)數(shù)組中出現(xiàn)過

                r.append(num)       # 則把該元素添加到結(jié)果中
                tmp.remove(num)     # 并且刪除另一個(gè)數(shù)組中的這條記錄
        return r                    # 返回結(jié)果列表

方案2：雙指針

我們首先對(duì)兩個(gè)數(shù)組進(jìn)行排序，然后分別用兩個(gè)指針從頭開始遍歷，如果遇到相同元素則記錄結(jié)果，如果不相等，則把數(shù)值較小的元素所在的指針向右移動(dòng)。

class Solution(object):
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        res = []                                    # 結(jié)果列表
        nums1.sort()                                # 排序數(shù)組1
        nums2.sort()                                # 排序數(shù)組2
        i = j = 0                                   # 初始化兩個(gè)遍歷指針
        while i < len(nums1) and j < len(nums2):    # 當(dāng)指針位置合法時(shí)
            if nums1[i] < nums2[j]:                 # 比較當(dāng)前各個(gè)指針?biāo)冈卮笮￡P(guān)系
                i += 1                              # 如果不相等，則根據(jù)大小關(guān)系移動(dòng)指針
            elif nums1[i] > nums2[j]:
                j += 1
            else:                                   # 如果相等
                res.append(nums1[i])                # 加入結(jié)果列表
                i += 1                              # 移動(dòng)兩個(gè)指針
                j += 1

        return res

如有疑問或建議，歡迎評(píng)論區(qū)留言~