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

Example:
Given nums1 = [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.

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?

思路

先对两个list进行排序，从nums1来开始看，对nums2来进行寻找。

如果找到相同的元素，就把元素记录到结果list当中。因为list是已经排好序了的，所以如果nums2此时的元素比nums1要大，说明nums1的迭代还没有到能够对应nums2位置的部分。反之亦然。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution(object):
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        result = []
        pos = 0
        len1 = len(nums1)
        len2 = len(nums2)
        if ((not len1) or (not len2)):
            return result
        else:
            nums1.sort()
            nums2.sort()
            for i in nums1:
                if (pos == len2):
                    break
                while(pos < len2):
                    if (i == nums2[pos]):
                        pos += 1
                        result.append(i)
                        break
                    elif (i > nums2[pos]):
                        pos += 1
                    else:
                        break
            return result

其实还可以用哈希表来做这道题，比双指针更加简单明了。

https://discuss.leetcode.com/topic/45893/c-hash-table-solution-and-sort-two-pointers-solution-with-time-and-space-complexity