완전히 칠해진 첫 번째 행 또는 열

2661. 처음으로 완전히 칠해진 행 또는 열

난이도:중

주제: 배열, 해시 테이블, 행렬

0-인덱스 정수 배열 arr과 m x n 정수 행렬 mat가 제공됩니다. arr과 mat는 모두 [1, m * n] 범위의 정수를 모두 포함합니다.

인덱스 0부터 시작하여 arr의 각 인덱스 i를 살펴보고 정수 arr[i]가 포함된 mat의 셀을 그립니다.

행이나 열이 매트에 완전히 칠해지는 가장 작은 인덱스 i를 반환합니다.

예 1:

• 입력: arr = [1,3,4,2], mat = [[1,4],[2,3]]
• 출력: 2
• 설명: 동작은 순서대로 표시되며 행렬의 첫 번째 행과 두 번째 열은 모두 arr[2]에서 완전히 그려집니다.

예 2:

• 입력: arr = [2,8,7,4,1,3,5,6,9], mat = [[3,2,5],[1,4,6],[ 8,7,9]]
• 출력: 3
• 설명: 두 번째 열은 arr[3]에서 완전히 칠해집니다.

제약조건:

• m == mat.length
• n = mat[i].length
• arr.length == m * n
• 1 5
• 1 5
• 1
• arr의 모든 정수는 고유합니다.
• mat의 모든 정수는 고유합니다.

힌트:

1. 주파수 배열을 사용할 수 있나요?
2. 행렬에서 값의 위치를 ​​사전 처리합니다.
3. 배열을 순회하고 사전 처리된 위치를 사용하여 해당 행 및 열 빈도를 증가시킵니다.
4. 행 빈도가 열 수와 같거나 그 반대인 경우 현재 인덱스를 반환합니다.

해결책:

다음 단계를 따르세요.

접근하다

1. 요소 위치 사전 처리:

   • 먼저 행렬의 요소 위치를 저장해야 합니다. 행렬의 각 값을 해당 (행, 열) 위치에 매핑하는 사전(position_map)을 만들 수 있습니다.

2. 주파수 배열:

   • 두 개의 주파수 배열이 필요합니다. 하나는 행용이고 다른 하나는 열용입니다.
   • arr 배열을 진행하면서 각 요소에 대한 해당 행과 열의 빈도가 증가합니다.

3. 전체 행 또는 열 확인:

   • 각 증분 후에 행이나 열이 완전히 칠해졌는지 확인하세요(즉, 빈도가 행렬의 열이나 행 크기에 도달하는지 확인하세요).
   • 그렇다면 현재 인덱스를 반환하세요.

4. 결과 반환:

   • 행이나 열 중 하나가 완전히 칠해진 인덱스가 우리의 답입니다.

세부 단계

1. mat의 각 값에 대해 해당 (행, 열) 위치에 대한 position_map 맵을 만듭니다.
2. row_count 및 col_count 배열을 만들어 각 행과 열에 칠해진 셀 수를 추적합니다.
3. arr을 순회하고 각 요소에 대해 해당 행과 열 수를 업데이트합니다.
4. 행이나 열이 완전히 칠해진 경우 해당 인덱스를 반환하세요.

PHP에서 이 솔루션을 구현해 보겠습니다: 2661. 처음으로 완전히 칠해진 행 또는 열

<?php /**
 * @param Integer[] $arr
 * @param Integer[][] $mat
 * @return Integer
 */
function firstCompleteIndex($arr, $mat) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$arr = [1, 3, 4, 2];
$mat = [[1, 4], [2, 3]];
echo firstCompleteIndex($arr, $mat); // Output: 2

$arr = [2, 8, 7, 4, 1, 3, 5, 6, 9];
$mat = [[3, 2, 5], [1, 4, 6], [8, 7, 9]];
echo firstCompleteIndex($arr, $mat); // Output: 3
?>

설명:

1. 전처리 위치:

   • 매트의 각 값이 해당 (행, 열) 위치에 매핑되는 사전 position_map을 만듭니다. 이는 arr을 순회하는 동안 일정한 시간에 모든 값의 위치에 직접 액세스하는 데 도움이 됩니다.

2. 빈도 계산:

   • row_count 및 col_count 배열을 0으로 초기화합니다. 이 배열은 특정 행이나 열의 셀이 몇 번이나 칠해졌는지 추적합니다.

3. 배열 순회:

   • arr의 각 값에 대해 position_map에서 해당 위치를 조회한 다음 해당 행과 열 개수를 늘립니다.
   • 개수를 업데이트한 후 행이나 열이 전체 크기에 도달했는지 확인합니다(예: row_count[$row] == n 또는 col_count[$col] == m). 그렇다면 현재 인덱스 i를 반환합니다.

4. 반품 결과:

   • 행이나 열 중 하나가 완전히 칠해진 첫 번째 인덱스를 반환합니다.

시간 복잡도:

• 전처리: O(m * n)으로 position_map을 만듭니다.
• 순회: arr(길이가 m * n임)의 각 요소를 처리하고 각 요소에 대해 상수 시간 작업을 수행하여 행 및 열 빈도를 업데이트하고 확인합니다. 이는 O( 1) 시간.
• 전체적으로 시간 복잡도는 O(m * n)입니다.

공간 복잡도:

• 모든 요소의 위치를 ​​position_map에 저장하고, 주파수 배열에는 O(m n) 공간을 사용합니다. 따라서 공간 복잡도는 O(m * n)입니다.

이 솔루션은 주어진 제약 내에서 문제를 효율적으로 처리해야 합니다.

연락처 링크

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

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

• 링크드인
• 깃허브

위 내용은 완전히 칠해진 첫 번째 행 또는 열의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!