2661。第一個完全繪製的行或列
難度：中
主題：陣列、雜湊表、矩陣
給你一個0索引整數數組arr，和一個m x n整數矩陣 mat。 arr 和 mat 都包含 all 範圍 [1, m * n] 內的整數。
從索引 0 開始遍歷 arr 中的每個索引 i，並在包含整數 arr[i] 的 mat 中繪製單元格。
傳回行或列將在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 的所有整數唯一.
提示：
- 我們可以使用頻率數組嗎？
- 預處理矩陣中值的位置。
- 遍歷陣列並使用預處理的位置遞增對應的行和列頻率。
- 如果行頻率等於列數，反之亦然，則傳回目前索引。
解：
我們可以按照以下步驟操作：
方法
-
預處理元素的位置:
- 首先，我們需要儲存矩陣中元素的位置。我們可以建立一個字典 (position_map)，將矩陣中的每個值對應到其 (row, col) 位置。
-
頻率數組:
- 我們需要兩個頻率數組：一個用於行，一個用於列。
- 當我們遍歷 arr 陣列時，我們將增加每個元素各自行和列的頻率。
-
檢查完整的行或欄位:
- 每次增量後，檢查是否有行或列被完全繪製（即其頻率達到矩陣列或行的大小）。
- 如果是，則傳回目前索引。
-
回傳結果:
詳細步驟
- 為mat中的每個值建立一個映射position_map到它的(row, col)位置。
- 建立數組 row_count 和 col_count 來追蹤每行和列中繪製的單元格的數量。
- 遍歷arr，對於每個元素，更新各自的行數和列數。
- 如果在任何時候行或列被完全繪製，則傳回該索引。
讓我們用 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
?>
登入後複製
解釋：
-
預處理位置:
- 我們建立一個字典position_map，其中mat中的每個值都對應到其（行，列）位置。這有助於在遍歷 arr 的過程中，在常數時間內直接存取任意值的位置。
-
頻率計數:
- 我們用零初始化 row_count 和 col_count 陣列。這些陣列將追蹤特定行或列中的儲存格被繪製的次數。
-
遍歷陣列:
- 對於arr中的每個值，我們在position_map中尋找其位置，然後遞增對應的行數和列數。
- 更新計數後，我們檢查是否有任何行或列已達到其完整大小（即 row_count[$row] == n 或 col_count[$col] == m）。如果是，我們傳回目前索引 i。
-
回傳結果:
時間複雜度：
-
預處理：我們在 O(m * n) 中建構position_map。
-
遍歷：我們處理arr的每個元素（長度為m * n），對於每個元素，我們執行常數時間操作來更新和檢查行頻率和列頻率，這需要O( 1) 時間。
- 整體來說，時間複雜度為O(m * n)。
空間複雜度：
- 我們將所有元素的位置儲存在position_map中，並且我們使用O(m n)空間作為頻率陣列。因此，空間複雜度為O(m * n)。
該解決方案應該在給定的限制內有效地處理問題。
聯絡連結
如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！
如果您想要更多類似的有用內容，請隨時關注我：
以上是第一個完全繪製的行或列的詳細內容。更多資訊請關注PHP中文網其他相關文章！
