配列を比較する方法

9666 ワード
algorithms javascript テキストリンク
この記事では、典型的なインタビュースタイルの質問を解決する2つの方法を示します.最初の解決策はより明白で効率が悪い.第2の解決策は大きな問題解決ツールを導入します:周波数カウンターオブジェクト.
ここでは、この記事を読んで得られるものです.
  • 問題に接近するためのフレームワーク
  • は、テクニック
    • を解決している非常に有用な、非常に高性能の問題
  • 機能を分析し、性能を改善する能力
    • 閉じるこの動画はお気に入りから削除されています.あなたがビデオを楽しむならば、購読を考慮してください.

    問題
    "二つの配列をとる"quared "という関数を書きます.配列のすべての値が2番目の配列で値を二乗した場合、この関数はtrueを返す必要があります.値の周波数は同じでなければなりません」
    ――インタビュアー
    まず最初に、私はあなたに問題を解決する「Na - State - ve」方法を示します.
    次に、“周波数カウンターオブジェクト”を使用して問題を解決する効率的な方法を示します.これはあなたの問題解決ツールボックス(あなたの脳)を持っている非常に便利なテクニックです.

    問題を理解する
    問題解決101:解決策を書く前に、問題を理解することは非常に重要です.これらの例を使用して、ソリューションが正しく動作していることを確認できます.
    例:
    ( 2 , 3 , 3 , [ 9 , 1 , 4 ]]/true ( 2 , 3 , 3 , 1 , 4 ])/false ( 2 , 2 , 3 , [ 4 , 9 , 9 ])/false 例1はtrueです.
  • 12 = 1 ( EYP ,それは配列2の)
  • 22 = 4 ( EYP ,それは配列2の)
  • 32 = 9 ( EYP ,それは配列2の)
    • 例2はfalseです.
  • 12 = 1 ( EYP ,それは配列2の)
  • 22 = 4 ( EYP ,それは配列2の)
  • 32 = 9
    例3はfalseです.
  • 22 = 4 (配列2のYep )
  • 22 = 4(nope、配列2の1つの4だけが)
  • 32 ( Yeep = 9 (はい)しかし、関数が事前にfalseを返したため、このチェックにも到達しません)

    ナイン・ウェイ
    最初に、配列が等しい長さでないかどうかを確認します.そうでなければ、値の頻度が同じであることができないので、我々はfalseを返して、機能から早く出て行きます.
    次に、ARR 1の各番号(num)をループします.ループの内部では、indexOf()を使用してARR 2でnum2の位置を探します.この値は変数foundIndexに代入される.
    値が見つからなかった場合、indexofは- 1を返す.したがって、私たちはFoundDindex = - 1であるかどうかチェックすることができて、そうならばfalseを返します.
    すべてが良いなら、私たちは移動して、splice()メソッドを使用してこの値をarr 2から削除します.これにより、両アレイの値の周波数は同じである.
    各番号をループした後、すべてのチェックを渡すと、我々はtrueを返すことができます.
    function squared(arr1, arr2) {
  if (arr1.length !== arr2.length) return false

  for (let num of arr1) {
    let foundIndex = arr2.indexOf(num ** 2)

    if (foundIndex === -1) return false

    arr2.splice(foundIndex, 1)
  }

  return true
}

    パフォーマンス
    このアルゴリズムは24579152(N 2)を持っています.なぜなら、最初の配列のすべての単一の項目をループして、このループの中で、2番目の配列(indexOf()で)のすべての単一の項目を最悪の場合にループしてしまうからです.
    あなたが知らない(または忘れてしまった)大きいものがあるならば、このビデオをチェックしてください.それは重要なトピックです!
    配列が長さnの場合、操作の数はN * N = N 2である.したがって、大きいO(N 2).
    ここで、第2の配列が各ループで短くなるので、これは全く真実ではありません.したがって、平均で、私たちは2番目の配列(0.5 n)の半分以上をループするだけです.大きいoはn＊0 . 5 n＝0 . 5 n 2である.しかし、大きいOは大きい絵ものを見ます、そして、入力が無限に接近するように、0.5は重要でないので、大きいO(N 2)に単純化します.
    Big O
    よりスマートな方法-周波数カウンターオブジェクト-ビッグO ( N )

    周波数カウンターオブジェクトは何ですか?
    周波数カウンタは、ものを集計するオブジェクトです.以下に2つの例を示します.

  • ナンバーが562479182に現れる回数
    周波数カウンタを使用すると、アルゴリズムのパフォーマンスを大幅に向上させることができます.
    ここで、[ 1 , 2 , 3 , 4 , 3 ]の周波数カウンターオブジェクトは次のようになります.
    let frequencyCounter = {
  1: 1,
  2: 1,
  3: 2,
  4: 1,
}
    すべての数字は1回、3から離れて表示されます.

    解決策
    周波数カウンターオブジェクトを作成するには、問題の配列をループします.それから、キーをつくって、現在の値+ 1の値を与えます、あるいは、我々がこの数に遭遇した最初であるならば、frequencyCounter[num]は未定義です、そして、したがって、我々は値を1に初期化します.
    私はループのために2つを使用しました、私はそれが読むのがより簡単であると感じたように、しかし、それはループのためにちょうど1でされることもできました.
    次に、周波数カウンタオブジェクトを比較することができる.まず、周波数カウンタ1の各キーが周波数カウンタ2のキーであるかどうかをチェックする.そうでない場合はfalseを返します.
    次に、周波数(値)が等しいかどうかを確認します.そうでない場合はfalseを返します.
    そして、我々がこの無傷のすべてを通り抜けるならば、我々は底に達して、真実を返します.
    function squared(arr1, arr2) {
  if (arr1.length !== arr2.length) return false

  let frequencyCounter1 = {}
  let frequencyCounter2 = {}

  // Create frequencyCounter1
  for (let num of arr1) {
    frequencyCounter1[num] = frequencyCounter1[num] + 1 || 1
  }

  // Create frequencyCounter2
  for (let num of arr2) {
    frequencyCounter2[num] = frequencyCounter2[num] + 1 || 1
  }

  // Compare frequency counters
  for (let key in frequencyCounter1) {
    if (!(key ** 2 in frequencyCounter2)) return false

    if (frequencyCounter1[key] !== frequencyCounter2[key ** 2]) return false
  }

  return true
}

    パフォーマンス
    周波数カウンタ1を作成する
  • 、ARR 1 => Nループ
    • のすべての数をループします
    のための
  • 同じ周波数
    周波数カウンタを比較するために
  • は、最悪の場合、Nループ
    • で、周波数カウンタ1のすべてのキーをループする
    total = n + n + n = 3 n
    大きなo(n)‐線形時間複雑さをもたらす.
    大きなO(N 2)の第二の努力よりもはるかに良い二次時間複雑さ.

    恐ろしい引用
  • 私は、アルゴリズムとデータ構造の私の知識のほとんどすべてを1つの目立つコースに知らせることができます.
    • あなたが本を好むならば、

    • あなたがこのポストを楽しんだならば、購読を考慮してください-それは非常に有り難いです!
    読書ありがとう.
    良い一日を!
    Androidプロトタイプデザインモード
    サーブレット出力ストリームgetoputStream()