두 배열의 접두사 공통 배열 찾기

2657. 두 배열의 접두사 공통 배열 찾기

난이도:중

주제: 배열, 해시 테이블, 비트 조작

길이가 n인 두 개의 인덱스가 0인 정수 순열 A와 B가 제공됩니다.

A와 B의 접두사 공통 배열은 C[i]가 A와 B 모두에서 인덱스 i 또는 그 앞에 존재하는 숫자의 개수와 동일한 배열 C입니다.

A와 B의 접두사 공통 배열을 반환합니다.

n개의 정수 시퀀스가 ​​1부터 n까지의 모든 정수를 정확히 한 번 포함하는 경우 순열이라고 합니다.

예 1:

• 입력: A = [1,3,2,4], B = [3,1,2,4]
• 출력: [0,2,3,4]
• 설명: i = 0: 공통된 숫자가 없으므로 C[0] = 0입니다.
  • i = 1:1과 3이 A와 B에서 공통이므로 C[1] = 2입니다.
  • i = 2에서 A와 B에서는 1, 2, 3이 공통이므로 C[2] = 3입니다.
  • i = 3에서: 1, 2, 3, 4는 A와 B에서 공통이므로 C[3] = 4입니다.

예 2:

• 입력: A = [2,3,1], B = [3,1,2]
• 출력: [0,1,3]
• 설명: i = 0: 공통된 숫자가 없으므로 C[0] = 0입니다.
  • i = 1: A와 B에는 3만 공통이므로 C[1] = 1입니다.
  • i = 2에서 A와 B에서는 1, 2, 3이 공통이므로 C[2] = 3입니다.

제약조건:

• 1
• 1
• A와 B는 모두 n 정수의 순열임이 보장됩니다.

힌트:

1. 인덱스 i까지 각 숫자의 발생 횟수를 저장하는 빈도 배열을 유지하는 것이 좋습니다.
2. 숫자가 두 번 발생했다면 A와 B 모두에서 발생했다는 의미이므로 둘 다 순열이므로 답에 1을 추가하세요.

해결책:

두 배열의 현재 인덱스 또는 그 이전에 발생한 숫자를 추적하면서 두 배열 A와 B를 반복할 수 있습니다. 두 배열 모두 동일한 숫자 집합의 순열이므로 두 개의 해시 집합(또는 배열)을 활용하여 두 배열의 현재 인덱스 또는 그 이전에 어떤 숫자가 나타나는지 저장할 수 있습니다. 각 인덱스에 대해 해당 시점까지 두 배열에 모두 나타난 공통 숫자를 계산할 수 있습니다.

솔루션 접근 방식:

1. 두 개의 배열을 사용하여 A와 B 모두에서 인덱스 i까지 숫자의 발생을 추적합니다.
2. 각 인덱스 i에 대해 A[i]와 B[i]가 모두 이전에 본 적이 있는지 확인합니다. 그렇다면 공통 개수를 늘리세요.
3. 주파수 배열을 사용하여 두 배열 모두에서 1부터 n까지의 숫자 존재를 추적합니다.

PHP에서 이 솔루션을 구현해 보겠습니다: 2657. 두 배열의 접두사 공통 배열 찾기

<?php /**
 * @param Integer[] $A
 * @param Integer[] $B
 * @return Integer[]
 */
function findThePrefixCommonArray($A, $B) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$A = [1, 3, 2, 4];
$B = [3, 1, 2, 4];
print_r(findThePrefixCommonArray($A, $B)); // Output: [0, 2, 3, 4]

$A = [2, 3, 1];
$B = [3, 1, 2];
print_r(findThePrefixCommonArray($A, $B)); // Output: [0, 1, 3]
?>

설명:

1. 주파수 배열: 두 개의 주파수 배열인 freqA와 freqB를 유지합니다. 여기서 각 인덱스는 순열의 숫자를 나타냅니다.
   • A[i] 또는 B[i]에서 숫자를 발견하면 주파수 배열에서 해당 값을 증가시킵니다.
2. 공통 개수: A[i]와 B[i] 모두에 대한 주파수 배열을 업데이트한 후 각 숫자가 인덱스 i까지 두 배열에 모두 나타나는지 확인합니다. 그렇다면 commonCount를 늘립니다.
3. 결과: 각 인덱스에 대한 결과 배열에 공통 개수가 저장됩니다.

예제 연습:

입력:

$A = [1, 3, 2, 4];
$B = [3, 1, 2, 4];

• i = 0: 아직 공통 숫자가 없음 → C[0] = 0
• i = 1: 숫자 1과 3이 공통 → C[1] = 2
• i = 2일 때: 숫자 1, 2, 3이 공통 → C[2] = 3
• i = 3일 때: 1, 2, 3, 4의 숫자가 공통 → C[3] = 4

출력: [0, 2, 3, 4]

시간 복잡도:

• O(n²⁾: 각 인덱스 i에 대해 1부터 n까지의 모든 요소를 ​​검사하여 공통적인지 확인하므로 이 솔루션은 시간 복잡도가 2차가 됩니다. n ≤ 50.
제약 조건을 고려하면 이는 허용됩니다.

주어진 제약 내에서 효과적으로 작동해야 합니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.

• 링크드인
• 깃허브

위 내용은 두 배열의 접두사 공통 배열 찾기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!