問題描述

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

補(bǔ)充說(shuō)明：

這個(gè)題目給定了兩個(gè)字符串，從這兩個(gè)字符串里找到他們的最大公約子串。

方案分析

1. 你要排序后找子串，我也沒辦法，這個(gè)方式能顯示，但是我不會(huì)這么做。
2. 尋找兩個(gè)字符串的最大子串，首先想到的肯定是統(tǒng)計(jì)兩個(gè)字符串中出現(xiàn)哪些字符，很容易就想到了hash的方式。
3. 借助上面的思想，如果發(fā)現(xiàn)字符1在字符串1中出現(xiàn)了2次，而在字符串2中出現(xiàn)了3次，那么很明顯這個(gè)結(jié)果中只能包含2次字符1。
4. 進(jìn)一步思考，先對(duì)字符串1生成hash結(jié)果，統(tǒng)計(jì)每個(gè)字符出現(xiàn)的次數(shù)。然后遍歷字符串2，如果字符串2中的字符出現(xiàn)在字符串1中，則減少hash結(jié)果中該字符的次數(shù)，并且把這個(gè)字符加入到結(jié)果集合中。這里需要進(jìn)行的控制就是：當(dāng)hash結(jié)果中的字符已經(jīng)=0的時(shí)候，下次發(fā)現(xiàn)該字符，就不能再減少了。
5. 這里如果要對(duì)中間結(jié)果的空間進(jìn)行節(jié)省，建議對(duì)字符串長(zhǎng)度短的那個(gè)進(jìn)行hash(并不能保證短的那個(gè)出現(xiàn)的字符少，但通常這樣認(rèn)為)。

python實(shí)現(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

1. 上面的程序?yàn)榱朔奖?，直接使用?code>collections這個(gè)庫(kù)生成字符hash，但沒有使用這個(gè)庫(kù)中的高級(jí)特性。python這個(gè)語(yǔ)言就是這么神奇，里面有你好多的想象不到的函數(shù)和操作。研讀python手冊(cè)，發(fā)現(xiàn)collections中的Counter已經(jīng)實(shí)現(xiàn)了這個(gè)程序要求的功能。
2. 下面代碼中的&運(yùn)算符很變態(tài)有木有。

python實(shí)現(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