フロントエンドとアルゴリズムleetcode 350.2つの配列の交差II

目次

#フロントエンドとアルゴリズムleetcode 350.2つの配列の交差II

タイトル説明

概要

ヒント

解析

解法一:ハッシュテーブル

解法二:二重ポインタ

解法3:暴力法

アルゴリズム

#フロントエンドとアルゴリズムleetcode 350.2つの配列の交差II
タイトルの説明
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つの配列に現れる回数と一致する必要があります.

出力結果の順序を考慮しなくてもいいです.

ステップ:

与えられた配列が順序付けされている場合?アルゴリズムをどのように最適化しますか?

nums 1のサイズがnums 2よりずっと小さい場合、どの方法が優れていますか?

nums 2の要素がディスクに格納されている場合、ディスクメモリは限られており、すべての要素を一度にメモリにロードすることはできません.どうすればいいですか?

350.2つの配列の交差II
概要
この問題は従来のマッピング問題と見なすことができ、各値の出現回数を知る必要がある.マッピング関係は、まず配列1中のすべての要素の出現回数を統計し、配列2を遍歴すればよい.配列2中の要素が存在し、1より大きい場合は、同じものが見つかったことを示し、値が1に等しい場合は、直接削除する[1].
ヒント
ハッシュ表、ダブルポインタ、暴力
解析
解法一:ハッシュテーブル
時間複雑度O(n)はまずHashmapで最初の配列の要素「keyに置く」と出現回数「valueに置く」を記録する.次に2番目の配列を巡り、対応する要素が見つかったら、この要素を戻り配列に追加します.value値が1より大きい場合、HashMapのvalue値は1を減らし、同じものが見つかったことを示します.value値が1に等しい場合は、要素を削除します.[2]
解法二:二重ポインタ
2つの配列を並べ替え、2つのポインタの初期値を0にし、2つのポインタの要素が等しいかどうかを比較すると、戻り配列に配置されます.2つのポインタは同時に前に進み、等しくない要素の小さいポインタは前に進みます.もし等しいなら、比較した要素は役に立たないに違いありません.2つのポインタは前に進みます.等しくない場合は大きな要素が小さい配列に存在するため、要素の小さい配列ポインタを前にします
解法三:暴力法
時間複雑度O(n^2)は、1番目の配列を巡回し、2番目の配列は、indexOfに現在の要素があるかどうかを検索する.
アルゴリズム#アルゴリズム#

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function (nums1, nums2) {
// hash 
  const [hash,res] = [new Map(),[]]
  nums1.forEach(el=>{
    if (hash.has(el)) {
      hash.set(el, hash.get(el) + 1)
    } else {
      hash.set(el, 1)
    }
  })
  nums2.forEach(el=>{
    const hashKey = hash.get(el)
    if (hash.has(el)) {
      res.push(el)
      if (hashKey > 1) {
        hash.set(el, hashKey - 1)
      } else {
        hash.delete(el)
      }
    }
  })
  return res
//   //     
//   let p1 = 0
//   let p2 = 0
//   let res = []
//   nums1 = nums1.sort((a, b) => a - b)
//   nums2 = nums2.sort((a, b) => a - b)
//   while (p1 < nums1.length && p2 < nums2.length) {
//     if (nums1[p1] == nums2[p2]) {
//       res.push(nums1[p1])
//       p1++
//       p2++
//     } else if (nums1[p1] < nums2[p2]) {
//       p1++
//     } else {
//       p2++
//     }
//   }
//   return res
//   //    
// const res = []
// if (nums1.length < nums2.length) [nums1, nums2] = [nums2, nums1]
// for (let i = 0; i < nums1.length; i++) {
//   const key = nums2.indexOf(nums1[i])
//   if (key !== -1) res.push(nums2.splice(key, 1))
// }
// return res
}

[1, 2], [11, 1, 2, 3, 2]に転送された実行結果

[ 1, 2 ]

実行結果

     :56 ms,     javascript       99.55%    
     :34.7 MB,     javascript       53.72%