[データ構造/アルゴリズム]11101 getItemFromTwoSortedArray#バイナリ検索アプリケーション#while文

📌 2つの整列配列からアイテムを抽出

質問する 長さm,nで昇順に並べられた自然配列を入力して、すべての要素のk番目の要素を返します。 入力 パラメータ1:arr 1 自然数を要素とする配列 arr1.長さm パラメータ2:arr 2 自然数を要素とする配列 arr2.長さn パラメータ3:k numberタイプの0より大きい整数 しゅつりょく numberタイプを返す必要があります。 注意事項 2つの配列の長さの合計は1000000未満です。 いくつかの配列arrのk番目の要素はarr[k−1]を表す。

問題をよく読んで、コードを書きます.昇順で並んでいることを確認すべきです.時間の複雑さを高度に解決するには、コードがより複雑になります.

第一の方法

二つの配列を統合しなければならないと思ったことがあります.次に、前に解いたバイナリ検索を適用するよう求められたので、左インデックスの中間のインデックスと右インデックスを割り当てて開始しました.もちろんそう書いた時はそうではなかった気がしますがㅠ

//2つの並べ替え、並べ替え let newArr = arr1.concat(arr2) let sortArr = newArr.sort((a,b) => a-b) //左、右インデックスの半分。 let left = 0 let right = sortArr.length - 1 while(left <= right) { const mid = parseInt((left + right)/2) for(let k=0; i < sortArr.length; i++) { if(sortArr[k-1] === sortArr[mid]) { return sortArr[k-1] } else { if(sortArr[k-1] < sortArr[mid]) { right = mid -1 } else { left = mid + 1} } } } };

☑ naive solution

これは、時間の複雑さを解決できない順序クエリー方法です.

count、左、右の変数を設定します.初期値は0です.そしてtarget宣言targetは、対応するインデックスの値(インデックスではない)

です.

countがkより大きい場合は常に繰り返されるため、while文

を記述する.

同時ドア内でarrが左より大きい場合は右、大きくない場合は右に分けられます.(初期値は0なのでarr 1/arr 2の0番目のインデックス間で比較します.)

arr 1[右]の値がarr 2[右]より大きい場合、target=arr 1[左]が割り当てられる.right++、

もあります

arr 1[右]の値がarr 2[左]より大きい場合、target=arr[左]
left++、

もあります
次の2つの部分はコードの説明を見たほうがいいです.

const getItemFromTwoSortedArrays = function (arr1, arr2, k) { let count = 0, left = 0, right = 0; let target; while (count < k) { if (arr1[left] < arr2[right]) { target = arr1[left]; // 検索を続けると、countも増加します。ドアを出た瞬間、インデックスの値が出てきました。 left++; } else { target = arr2[right]; // 検索を続けると、countも増加します。ドアを出た瞬間、インデックスの値が出てきました。 right++; } count++; } return target; };