第一個完全繪製的行或列

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 的所有整數唯一.

提示：

1. 我們可以使用頻率數組嗎？
2. 預處理矩陣中值的位置。
3. 遍歷陣列並使用預處理的位置遞增對應的行和列頻率。
4. 如果行頻率等於列數，反之亦然，則傳回目前索引。

解：

我們可以按照以下步驟操作：

方法

1. 預處理元素的位置:

   • 首先，我們需要儲存矩陣中元素的位置。我們可以建立一個字典 (position_map)，將矩陣中的每個值對應到其 (row, col) 位置。

2. 頻率數組:

   • 我們需要兩個頻率數組：一個用於行，一個用於列。
   • 當我們遍歷 arr 陣列時，我們將增加每個元素各自行和列的頻率。

3. 檢查完整的行或欄位:

   • 每次增量後，檢查是否有行或列被完全繪製（即其頻率達到矩陣列或行的大小）。
   • 如果是，則傳回目前索引。

4. 回傳結果:

   • 行或列被完全繪製的索引就是我們的答案。

詳細步驟

1. 為mat中的每個值建立一個映射position_map到它的(row, col)位置。
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，其中mat中的每個值都對應到其（行，列）位置。這有助於在遍歷 arr 的過程中，在常數時間內直接存取任意值的位置。

2. 頻率計數:

   • 我們用零初始化 row_count 和 col_count 陣列。這些陣列將追蹤特定行或列中的儲存格被繪製的次數。

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 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是第一個完全繪製的行或列的詳細內容。更多資訊請關注PHP中文網其他相關文章！