トピックの分析
まずはトピックを見てみましょう：
| 2つの配列が与えられたとき、それらの交点を計算する関数を書きなさい。 |
例1.
: nums1 = [1,2,2,1], nums2 = [2,2]
: [2,2]
例2.
: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
: [4,9]
説明
- 各要素が出力に現れる回数は、その要素が両方の配列に現れる回数と一致しなければなりません。
- 出力結果の順序は無視できます。
上級者向け。
- 与えられた配列が既に順序付けされている場合は？アルゴリズムはどのように最適化されますか？
アイデア：2つのポインタを0にセットし、2つのポインタの要素が等しいかどうかを比較します。ポインタの要素が等しい場合は、両方のポインタを一緒に後方に移動し、等しい要素を空白の配列に入れます。
問題分析
まず、この問題が出題されたとき、基本的にすぐに、この問題は伝統的な写像の問題であると考えることができます。なぜこのように考えることができるかというと、2つの配列の交差要素を求める必要があり、同時に、2つの配列に出現する回数と同じである必要があるからです。<元素,出现次数>このことから、各値の出現回数を知る必要があり、対応関係は.あとは順風満帆に問題を解くことができます。
この解決策はあまりにも単純なので、それ以上の分析はせずに、問題の解決策を直接示します：
//GO
func intersect(nums1 []int, nums2 []int) []int {
m0 := map[int]int{}
for _, v := range nums1 {
//nums1を反復処理し、初期化するmap
m0[v] += 1
}
k := 0
for _, v := range nums2 {
//要素が等しい場合、それらをnums2に入れ、その配列に現れる1
if m0[v] > 0 {
m0[v] -=1
nums2[k] = v
k++
}
}
return nums2[0:k]
}
これは比較的簡単な方法で、誰でも分かると思います！
トピックの前進
与えられた配列がすでに順序付けされていたら？どのようにアルゴリズムを最適化しますか？arr1=[1,2,3,4,4,13]、arr2=[1,2,3,9,10] img[src*="#thumbnail"] { zoom: 50%; height:100px; } のように両方の配列が順番に並んでいるとします。
すでにソートされた2つの配列がある場合、ダブル・ポインタを使った解決策を考えるのは簡単です。
問題解決の手順は以下の通りです：
<1>2つのポインタを0にセットし、2つのポインタの要素が等しいかどうかを比較します。 ポインタの要素が等しい場合は、2つのポインタを一緒に後方に移動し、等しい要素を空の配列に入れます。次の図では、ポインタは最初の要素を指しており、要素が等しいと判断した後、同じ要素を空の配列に入れています。
<2>2つのポインタの要素が等しくなければ、小さい方のポインタを後ろに動かします。 図のポインタは次の要素に移動し、要素が等しくないと判定した後、要素の小さい方のポインタを後ろに移動して判定を続けます。
<3>上記の手順を繰り返します。
<4>配列のいずれかが終了するまで。
、タイトル回答
この分析に基づけば、次のような解答を得ることは容易です：
//GO
func intersect(nums1 []int, nums2 []int) []int {
i, j, k := 0, 0, 0
sort.Ints(nums1)
sort.Ints(nums2)
for i < len(nums1) && j < len(nums2) {
if nums1[i] > nums2[j] {
j++
} else if nums1[i] < nums2[j] {
i++
} else {
nums1[k] = nums1[i]
i++
j++
k++
}
}
return nums1[:k]
}
ヒント: このソリューションでは空白の配列は作成されません。使用する配列に等しい要素を入れることで、スペースを節約することができます。
私が書いたすべての解答と各問題の完全な図解をeBookにまとめました。クリックしてダウンロード
