问题描述
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?
Subscribe to see which companies asked this question
补充说明：
这个题目给定了两个字符串，从这两个字符串里找到他们的最大公约子串。
方案分析
- 你要排序后找子串，我也没办法，这个方式能显示，但是我不会这么做。
- 寻找两个字符串的最大子串，首先想到的肯定是统计两个字符串中出现哪些字符，很容易就想到了hash的方式。
- 借助上面的思想，如果发现字符1在字符串1中出现了2次，而在字符串2中出现了3次，那么很明显这个结果中只能包含2次字符1。
- 进一步思考，先对字符串1生成hash结果，统计每个字符出现的次数。然后遍历字符串2，如果字符串2中的字符出现在字符串1中，则减少hash结果中该字符的次数，并且把这个字符加入到结果集合中。这里需要进行的控制就是：当hash结果中的字符已经=0的时候，下次发现该字符，就不能再减少了。
- 这里如果要对中间结果的空间进行节省，建议对字符串长度短的那个进行hash(并不能保证短的那个出现的字符少，但通常这样认为)。
python实现
class Solution(object):
def intersect(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
import collections
temp_dict = {}
result = []
if len(nums1) > len(nums2):
temp_dict = collections.Counter(nums2)
for item in nums1:
if item in temp_dict and temp_dict[item] > 0:
temp_dict[item] -= 1
result.append(item)
else:
temp_dict = collections.Counter(nums1)
for item in nums2:
if item in temp_dict and temp_dict[item] > 0:
temp_dict[item] -= 1
result.append(item)
return result
方案分析2
- 上面的程序为了方便，直接使用了
collections这个库生成字符hash，但没有使用这个库中的高级特性。python这个语言就是这么神奇，里面有你好多的想象不到的函数和操作。研读python手册，发现collections中的Counter已经实现了这个程序要求的功能。 - 下面代码中的
&运算符很变态有木有。
python实现2
def intersect(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
import collections
result = []
for num, count in (collections.Counter(nums1) & collections.Counter(nums2)).items():
result += [num] * count
return result
