2661。第一個(gè)完全繪製的行或列

難度：中

主題：陣列、雜湊表、矩陣

給你一個(gè)0索引整數(shù)數(shù)組arr，和一個(gè)m x n整數(shù)矩陣 mat。 arr 和 mat 都包含 all 範(fàn)圍 [1, m * n] 內(nèi)的整數(shù)。

從索引 0 開始遍歷 arr 中的每個(gè)索引 i，並在包含整數(shù) arr[i] 的 mat 中繪製單元格。

傳回行或列將在mat中完全繪製的最小索引i。

範(fàn)例1：

• 輸入： arr = [1,3,4,2], mat = [[1,4],[2,3]]
• 輸出： 2
• 解釋： 走法依序顯示，矩陣的第一行和第二列都在 arr[2] 處完全繪製。

範(fàn)例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 的所有整數(shù)唯一.
• mat 的所有整數(shù)唯一.

提示：

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

解：

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

方法

1. 預(yù)處理元素的位置:

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

2. 頻率數(shù)組:

   • 我們需要兩個(gè)頻率數(shù)組：一個(gè)用於行，一個(gè)用於列。
   • 當(dāng)我們遍歷 arr 陣列時(shí)，我們將增加每個(gè)元素各自行和列的頻率。

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

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

4. 回傳結(jié)果:

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

詳細(xì)步驟

1. 為mat中的每個(gè)值建立一個(gè)映射position_map到它的(row, col)位置。
2. 建立數(shù)組 row_count 和 col_count 來追蹤每行和列中繪製的單元格的數(shù)量。
3. 遍歷arr，對(duì)於每個(gè)元素，更新各自的行數(shù)和列數(shù)。
4. 如果在任何時(shí)候行或列被完全繪製，則傳回該索引。

讓我們用 PHP 實(shí)作這個(gè)解：2661。第一個(gè)完全繪製的行或列

<?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. 預(yù)處理位置:

   • 我們建立一個(gè)字典position_map，其中mat中的每個(gè)值都對(duì)應(yīng)到其（行，列）位置。這有助於在遍歷 arr 的過程中，在常數(shù)時(shí)間內(nèi)直接存取任意值的位置。

2. 頻率計(jì)數(shù):

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

3. 遍歷陣列:

   • 對(duì)於arr中的每個(gè)值，我們?cè)趐osition_map中尋找其位置，然後遞增對(duì)應(yīng)的行數(shù)和列數(shù)。
   • 更新計(jì)數(shù)後，我們檢查是否有任何行或列已達(dá)到其完整大?。?row_count[$row] == n 或 col_count[$col] == m）。如果是，我們傳回目前索引 i。

4. 回傳結(jié)果:

   • 傳回一行或列完全繪製的第一個(gè)索引。

時(shí)間複雜度：

• 預(yù)處理：我們?cè)?O(m * n) 中建構(gòu)position_map。
• 遍歷：我們處理arr的每個(gè)元素（長度為m * n），對(duì)於每個(gè)元素，我們執(zhí)行常數(shù)時(shí)間操作來更新和檢查行頻率和列頻率，這需要O( 1) 時(shí)間。
• 整體來說，時(shí)間複雜度為O(m * n)。

空間複雜度：

• 我們將所有元素的位置儲(chǔ)存在position_map中，並且我們使用O(m n)空間作為頻率陣列。因此，空間複雜度為O(m * n)。

該解決方案應(yīng)該在給定的限制內(nèi)有效地處理問題。

聯(lián)絡(luò)連結(jié)

如果您發(fā)現(xiàn)本系列有幫助，請(qǐng)考慮在 GitHub 上給 存儲(chǔ)庫 一個(gè)星號(hào)或在您最喜歡的社交網(wǎng)絡(luò)上分享該帖子？ 。您的支持對(duì)我來說意義重大！

如果您想要更多類似的有用內(nèi)容，請(qǐng)隨時(shí)關(guān)注我：

• 領(lǐng)英
• GitHub

以上是第一個(gè)完全繪製的行或列的詳細(xì)內(nèi)容。更多資訊請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！