サブシーケンスを作るための最小操作

これは一連のleetcode解決説明の一部です.あなたがこの解決法が好きであるか、それが役に立つとわかるならば、このポストと同様に/または上告my solution post on Leetcode's forumsをしてください.

Leetcode Problem #1713 (Hard): Minimum Operations to Make a Subsequence
説明
異なった整数と重複を持つことができる別の整数配列targetからなる配列arrが与えられます.
1つの操作では、arrの任意の位置に任意の整数を挿入できます.たとえば、arr = [1,4,1,2]ならば、中央に3を追加し、[1,4,3,1,2]にすることができます.配列の先頭または末尾に整数を挿入できます.targetをarrのサブシーケンスにするために必要な操作の最小数を返します.
配列のサブシーケンスは、残りの要素の相対順序を変更せずに、いくつかの要素を削除することによって、元の配列から生成された新しい配列です.例えば、[2,7,4]は[4,2,3,7,2,1,4]のサブシーケンスであり、[2,4,2]はそうではない.
例:
例1 :
入力
target =[ 5 , 1 , 3 ], arr =[ 9 , 4 , 2 , 3 , 4 ]
出力:
2
解説
ARR =[ 5 , 9 , 4 , 1 , 2 , 3 , 4 ]を作るようなウェイで5と1を追加することができます.
例2 :
入力
target =[ 6 , 4 , 8 , 1 , 3 , 2 ], arr =[ 4 , 7 , 6 , 2 , 3 , 8 , 6 , 1 ]
出力:
3
制約
1つは、目標です.長さ、長さr = 10 ^ 5

1 <= target [ i ], arr [ i ] <= 10 ^ 9

目標は、複製

を含みません
考え
通常、この問題を解決するのは、最長の一般的なサブシーケンスを識別することである.lcsアルゴリズムはo(m＊n)時間複雑性を持つが,この場合はあまりに長い.
この解決策は、実際には、tが個別の要素を持っていることを認識したら、より簡単です.これは、LCSアプローチの代わりに、代わりにTの要素をインデックスとして扱うことができ、代わりにO(n * log n)の時間複雑さを持つ最大の増加するサブシーケンスアプローチを使用してこれを解決することができます.
LISソリューションでは、まずリファレンスを使用するインデックスマップ(IMAP)を作成する必要があります.我々がそれを再構築することができる必要があるのではなく、残りのサブシーケンスの長さを必要とするだけであるので、私たちはちょうどLIS [ i ]が最も効率的な(I - 1)-長さ副シーケンスで最後の数を追跡する配列(LIS)を使用する必要があります.
言い換えれば、LIS [ 4 ]は、辞書上で最も小さい3 -数副シーケンスの最後の数であるでしょう.これらのサブシーケンスの各々が定義によって増加していなければならないので、そして、LISの各エントリーが副系列の各々の長さの最高の可能なバージョンを表すので、LISはその性質によって順序付けられた配列です.
これは、Aを通して繰り返している間に遭遇するどんな新しい数も(そして、IMAPを通して[ i ]を参照している)、より大きいLISの最初の利用可能なエントリを交換するのに用いられることができることを意味します.そして、LISが命じられるので、我々はLISの適切な置換インデックスを見つけるために単純なバイナリ検索を使用することができます.
一旦Aを通して繰り返されるならば、最も長く増加しているsusbequenceの長さはLISの長さに等しくなります.そして、それは同様にTとAの間で最も長い共通部分系列の長さです.
JavaScriptコード

var minOperations = function(T, A) {
    let imap = new Map(), lis = []
    for (let i = 0; i < T.length; i++) imap.set(T[i], i)
    for (let i = 0; i < A.length; i++) {
        let index = imap.get(A[i])
        if (index !== undefined)
            lis[find(index, lis)] = index
    }
    return T.length - lis.length
};

const find = (target, arr, left=0, right=arr.length) => {
    while (left <= right) {
        let mid = left + right >> 1
        if (arr[mid] < target) left = mid + 1
        else right = mid - 1
    }
    return left
}