問題描述
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
補充說明：
這個題目給定了兩個字符串，從這兩個字符串里找到他們的最大公約子串靠闭。
方案分析
- 你要排序后找子串澎媒，我也沒辦法儡陨，這個方式能顯示，但是我不會這么做蓄氧。
- 尋找兩個字符串的最大子串，首先想到的肯定是統(tǒng)計兩個字符串中出現(xiàn)哪些字符，很容易就想到了hash的方式咬扇。
- 借助上面的思想，如果發(fā)現(xiàn)字符1在字符串1中出現(xiàn)了2次廊勃，而在字符串2中出現(xiàn)了3次懈贺，那么很明顯這個結(jié)果中只能包含2次字符1。
- 進一步思考坡垫，先對字符串1生成hash結(jié)果梭灿，統(tǒng)計每個字符出現(xiàn)的次數(shù)。然后遍歷字符串2冰悠，如果字符串2中的字符出現(xiàn)在字符串1中堡妒，則減少hash結(jié)果中該字符的次數(shù)，并且把這個字符加入到結(jié)果集合中溉卓。這里需要進行的控制就是：當(dāng)hash結(jié)果中的字符已經(jīng)=0的時候皮迟，下次發(fā)現(xiàn)該字符，就不能再減少了桑寨。
- 這里如果要對中間結(jié)果的空間進行節(jié)省伏尼，建議對字符串長度短的那個進行hash(并不能保證短的那個出現(xiàn)的字符少，但通常這樣認為)尉尾。
python實現(xiàn)
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這個語言就是這么神奇辨图，里面有你好多的想象不到的函數(shù)和操作班套。研讀python手冊，發(fā)現(xiàn)collections中的Counter已經(jīng)實現(xiàn)了這個程序要求的功能徒役。 - 下面代碼中的
&運算符很變態(tài)有木有孽尽。
python實現(xiàn)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
