솔루션: 하위 시퀀스를 만들기 위한 최소 작업

이것은 일련의 Leetcode 솔루션 설명( )의 일부입니다. 이 솔루션이 마음에 드셨거나 유용하셨다면 이 게시물에 좋아요를 누르거나 추천my solution post on Leetcode's forums 해주세요.

Leetcode 문제 #1713(어려움): 하위 시퀀스를 만들기 위한 최소 작업

설명:

고유한 정수로 구성된 배열target과 중복을 가질 수 있는 또 다른 정수 배열arr이 제공됩니다.

한 번의 작업으로 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:



입력:
대상 = [5,1,3], arr = [9,4,2,3,4]

산출:
2

설명:
arr = [5,9,4,1,2,3,4]가 되도록 5와 1을 추가하면 target은 arr의 하위 시퀀스가 ​​됩니다.



예 2:



입력:
대상 = [6,4,8,1,3,2], arr = [4,7,6,2,3,8,6,1]

산출:
삼



제약 조건:

1 <= target.length, arr.length <= 10^5

1 <= 대상[i], arr[i] <= 10^9

대상에 중복 항목이 없습니다.

아이디어:

일반적으로 가장 긴 공통 부분 시퀀스를 식별하여 이 문제를 해결합니다. 이는 타겟 배열(T)을 가능한 일치시키기 위해 삽입해야 하는 요소 수를 나타내기 때문이기도 합니다. LCS 알고리즘은 O(m * n) 시간 복잡도를 갖지만 이 경우에는 너무 깁니다.

이 솔루션은 T가 별개의 요소를 가지고 있다는 것을 알게 되면 실제로 훨씬 더 간단합니다. 즉, LCS 접근 방식 대신에 T의 요소를 인덱스로 처리하고 대신 O(n * log n)의 시간 복잡도를 사용하여 가장 큰 증가 부분 시퀀스 접근 방식을 사용하여 해결할 수 있습니다.

LIS 솔루션에서는 먼저 참조를 사용하기 위해 인덱스 맵(imap)을 생성해야 합니다. 우리는 그것을 재구성할 필요 없이 가장 작은 부분 시퀀스의 길이만 필요하므로 lis[i]가 가장 효율적인(i-1 )-길이 부분 시퀀스.

다시 말해서, lis[4]는 사전식으로 가장 작은 3자리 숫자 하위 시퀀스의 마지막 숫자가 됩니다. 이러한 각 하위 시퀀스는 정의에 따라 증가해야 하고 lis의 각 항목은 하위 시퀀스의 각 길이에 대한 최상의 버전을 나타내므로 lis는 본질적으로 정렬된 배열입니다.

이것은 A를 반복하는 동안 발견한 새로운 숫자(imap을 통해 A[i] 참조)를 사용하여 더 큰 lis의 첫 번째 사용 가능한 항목을 대체하는 데 사용할 수 있음을 의미합니다. lis는 순서가 지정되어 있으므로 간단한 이진 검색을 사용하여 lis의 적절한 대체 인덱스를 찾을 수 있습니다.

A를 통해 반복을 완료하면 가장 긴 증가 부분 수열의 길이는 lis의 길이와 같을 것입니다. 이는 마찬가지로 T와 A 사이의 가장 긴 공통 부분 수열의 길이와 같습니다. 그 시점에서 우리가 해야 할 일은 T의 길이와의 차이를 반환하여 T를 완료하는 데 필요한 작업 수를 확인합니다.


자바스크립트 코드:

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
}