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

難度：中等

主題：數(shù)組、哈希表、矩陣

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

從索引 0 開(kāi)始遍歷 arr 中的每個(gè)索引 i，并在包含整數(shù) 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 的所有整數(shù)唯一.
• mat 的所有整數(shù)唯一.

提示：

1. 我們可以使用頻率數(shù)組嗎？
2. 預(yù)處理矩陣中值的位置。
3. 遍歷數(shù)組并使用預(yù)處理的位置遞增相應(yīng)的行和列頻率。
4. 如果行頻率等于列數(shù)，反之亦然，返回當(dāng)前索引。

解決方案：

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

方法

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

   • 首先，我們需要存儲(chǔ)矩陣中元素的位置。我們可以創(chuàng)建一個(gè)字典 (position_map)，將矩陣中的每個(gè)值映射到其 (row, col) 位置。

2. 頻率數(shù)組:

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

3. 檢查完整的行或列:

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

4. 返回結(jié)果:

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

詳細(xì)步驟

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

讓我們用 PHP 實(shí)現(xiàn)這個(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òu)建一個(gè)字典position_map，其中mat中的每個(gè)值都映射到其（行，列）位置。這有助于在遍歷 arr 的過(guò)程中，在常數(shù)時(shí)間內(nèi)直接訪問(wèn)任意值的位置。

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

   • 我們用零初始化 row_count 和 col_count 數(shù)組。這些數(shù)組將跟蹤特定行或列中的單元格被繪制的次數(shù)。

3. 遍歷數(shù)組:

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

4. 返回結(jié)果:

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

時(shí)間復(fù)雜度：

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

空間復(fù)雜度：

• 我們將所有元素的位置存儲(chǔ)在position_map中，并且我們使用O(m n)空間作為頻率數(shù)組。因此，空間復(fù)雜度為O(m * n)。

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

聯(lián)系鏈接

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

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

• 領(lǐng)英
• GitHub

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