Intersection of Two Arrays II

Given two arrays, write a function to compute their intersection.

Example: Givennums1=[1, 2, 2, 1],nums2=[2, 2], return[2, 2].

Note:

• Each element in the result should appear as many times as it shows in both arrays.

• The result can be in any order.

注意：如果为input：［1］，［1，1］，需要判断hashmap[num] > 0

class Solution(object):
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        #hashmap的index为nums的值，value为值出现的个数
        hashmap = {}
        result = []
        for num in nums1:
            if num in hashmap:
                hashmap[num] += 1
            else:
                hashmap[num] = 1

        for num in nums2:
            if num in hashmap and hashmap[num] > 0:
                result.append(num)
                hashmap[num] -= 1
        return result

二刷：

hashmap：

注意需要判断hashmap[num] > 0，因为如果不判断，nums1=［1］，nums2＝［1，1］会返回错误的result［1，1］

class Solution(object):
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        result = []
        hashmap=collections.Counter(nums1)
        for num in nums2:
            if num in hashmap and hashmap[num] > 0:
                hashmap[num] -= 1
                result.append(num)
        return result

Two Pointers:

先给两个数组排序，然后用两个指针分别指向两个数组的起始位置，如果两个指针指的数字相等，则存入结果中，两个指针均自增1，如果第一个指针指的数字大，则第二个指针自增1，反之亦然

class Solution(object):
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        i = j = 0
        result = []
        nums1, nums2 = sorted(nums1), sorted(nums2)
        while i < len(nums1) and j < len(nums2):
            if nums1[i] == nums2[j]:
                result.append(nums2[j])
                i+=1
                j+=1
            else:
                if nums1[i] > nums2[j]:
                    j += 1
                else:
                    i += 1
        return result