0630 每日一題(找出2個數組中的交集,返回的結果元素出現的次數必須與數組相同)

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.

 

Example 1:

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

Example 2:

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

 

Constraints:

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

 

Follow up:

• What if the given array is already sorted? How would you optimize your algorithm?
• What if nums1's size is small compared to nums2's size? Which algorithm is better?
• What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

class Solution:

    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:

        res=[] #初始化回傳的list

        freq={} #初始化紀錄出現頻率用的字典

        for i in nums1:

            freq[i]=freq.get(i,0) +1

            #如果元素尚未存入頻率字典 他會是0 + 1,反之則是freq[i]+1

       

        for i in nums2:

            if i in freq and freq[i]>0:

                #如果元素交集,記錄到res中,同時頻率-1, 當頻率為0則該值不在被記錄

                res.append(i)

                freq[i] -=1        

     

        return res

class Leetcode:

    def __init__(self,nums1,nums2):

        self.nums1=nums1

        self.nums2=nums2

        self.res=[]

        self.freq={}

    def intersect(self):

        for i in self.nums1:

            self.freq[i] = self.freq.get(i,0) +1

    #freq紀錄nums1每個元素出現頻率

    #get(key,val) 如果key存在就回傳字典中的值,

    #如果key不存在 就回傳get(key,val)中的val

       

        for i in self.nums2:

            if i in self.freq and self.freq[i] > 0:

    #nums2的元素存在紀錄的字典中, 並且每出現一次讓頻率-1,

    #直到頻率為0時,不再記錄到res

                self.res.append(i)

                self.freq[i] -=1

        return self.res

ans=Leetcode([1,2,2,1],[2,2])

ans2=Leetcode([4,9,5],[9,4,9,8,4])

ans3=Leetcode([61,24,20,58,95,53,17,32,45,85,70,20,83,62,35,89,5,95,12,86,58,77,30,64,46,13,5,92,67,40,20,38,31,18,89,85,7,30,67,34,62,35,47,98,3,41,53,26,66,40,54,44,57,46,70,60,4,63,82,42,65,59,17,98,29,72,1,96,82,66,98,6,92,31,43,81,88,60,10,55,66,82,0,79,11,81],[5,25,4,39,57,49,93,79,7,8,49,89,2,7,73,88,45,15,34,92,84,38,85,34,16,6,99,0,2,36,68,52,73,50,77,44,61,48])

print(ans.intersect())

print(ans2.intersect())

print(ans3.intersect())

-------------------------------------------終端機

[2, 2] [9, 4] [5, 4, 57, 79, 7, 89, 88, 45, 34, 92, 38, 85, 6, 0, 77, 44, 61]