350 Intersection of two arrays II

Original Description: Given two arrays, write a function to compute their intersection. —————————-

• 要求： 给两个数组，找出其重合。

---

• 返回： 重合部分

---

• 例子：
  • input: [1,2,2,1], [2,2]
  • output: [2,2]

---

Solution

给两数组排序，然后对两数组逐个元素比较，将重合部分放进结果。

class Solution(object):
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        
        # check length and sort
        
        if len(nums1) <= len(nums2):
            shorter = sorted(nums1)
            longer = sorted(nums2)
        else:
            shorter = sorted(nums2)
            longer = sorted(nums1)
        
        # use two pointers in each of the array
        s = 0
        l = 0
        out = []
        while s < len(shorter) and l < len(longer):
            if shorter[s] <longer[l]:
                s += 1
            elif shorter[s] >  longer[l]:
                l += 1
            else:
                out.append(shorter[s])
                s+=1
                l+=1
        return out