350.2つの配列の交差II(python)
7434 ワード
問題の説明
350.2つの配列の交差IIは2つの配列を与え、1つの関数を記述してそれらの交差を計算する.
例1:
例2:
説明:出力結果の各要素の出現回数は、2つの配列における要素の出現回数の最小値と一致する必要があります. 出力結果の順序を考慮しなくてもいいです.
もんだいぶんせきの直接的な考え方は、配列1を遍歴し、配列2に含まれているかどうかを確認し、もしそうであれば、配列2の要素を配列1が循環するまで削除することです.次に,長い配列(n)を配列1とするか,短い配列(m)を配列1とするかを考え,長い配列を遍歴し,短い配列に一致すると結論した.理由は以下の通りである:両方の場合の最悪の最適時間複雑度はO(m 2)O(m^2)O(m 2)、O(n^2)O(n^2)O(n 2)であるが、長い配列を巡る過程において、短い配列をマッチングするには、短い配列が空である場合にサイクルを破るため、長い配列を巡る時間複雑度が相対的に好ましいという条件がある.実験検証もそうだ. ハッシュ・テーブル構造を使用して、時間的複雑さをさらに最適化する.
インプリメンテーションコード
350.2つの配列の交差IIは2つの配列を与え、1つの関数を記述してそれらの交差を計算する.
例1:
：nums1 = [1,2,2,1], nums2 = [2,2]
：[2,2]
例2:
：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
：[4,9]
説明:
もんだいぶんせき
インプリメンテーションコード
#
class Solution(object):
def intersect(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
if len(nums1) > len(nums2):
res = self.find(nums1, nums2)
else:
res = self.find(nums2, nums1)
return res
def find(self, longnums, shortnums):
res = []
for i in range(len(longnums)):
if shortnums==[]:
break
if longnums[i] in shortnums:
res.append(longnums[i])
shortnums.remove(longnums[i])
return res
#
class Solution(object):
def intersect(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
res_dict = {}
res = []
for i in nums1:
if i in res_dict:
res_dict[i] += 1
else:
res_dict[i] = 1
for j in nums2:
if j not in res_dict:
continue
else:
if res_dict[j] == 0:
continue
else:
res.append(j)
res_dict[j] -= 1
return res