2661。最初に完全にペイントされた行または列

難易度: 中

トピック: 配列、ハッシュ テーブル、行列

0 インデックスの 整數配列 arr と、m x n 整數の 行列 マットが與えられます。 arr と mat には両方とも、[1, m * n] の範囲內の整數すべてが含まれています。

arr 內の各インデックス i をインデックス 0 から順に調べ、整數 arr[i] を含む mat 內のセルをペイントします。

マット內で行または列が完全にペイントされる最小のインデックス i を返します。

例 1:

• 入力: arr = [1,3,4,2]、mat = [[1,4],[2,3]]
• 出力: 2
• 説明: 動きが順番に表示され、行列の最初の行と 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
• 説明: 2 番目の列は arr[3] で完全にペイントされます。

制約:

• m == mat.length
• n = mat[i].length
• arr.length == m * n
• 1 5
• 1 5
• 1
• arr の整數はすべて 一意です。
• マットのすべての整數は 一意です。

ヒント:

1. 周波數配列を使用できますか?
2. 行列內の値の位置を前処理します。
3. 配列を走査し、前処理された位置を使用して、対応する行と列の頻度をインクリメントします。
4. 行頻度が列數と等しくなった場合、またはその逆の場合は、現在のインデックスを返します。

解決策:

次の手順に従うことができます:

アプローチ

1. 要素の位置を前処理します:

   • まず、行列內の要素の位置を保存する必要があります。行列內の各値をその (行、列) 位置にマップする辭書 (position_map) を作成できます。

2. 周波數配列:

   • 2 つの周波數配列が必要です。1 つは行用、もう 1 つは列用です。
   • arr 配列を調べていくと、各要素のそれぞれの行と列の頻度が増加します。

3. 完全な行または列をチェック:

   • 各増分後、行または列が完全にペイントされたかどうかを確認します (つまり、その頻度が行列の列または行のサイズに達する)。
   • そうであれば、現在のインデックスを返します。

4. 結果を返す:

   • 行または列のいずれかが完全にペイントされているインデックスが私たちの答えです。

詳細な手順

1. マット內の各値の (行、列) 位置へのマップ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. 前処理位置:

   • mat の各値がその (行、列) 位置にマップされる辭書のposition_map を構築します。これは、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 を構築します。
• Traversal: arr の各要素 (長さは m * n) を処理し、各要素に対して定數時間操作を実行して行と列の頻度を更新およびチェックします。これには O( がかかります) 1) 時間。
• 全體として、時間計算量は O(m * n) です。

空間の複雑さ:

• すべての要素の位置をposition_mapに保存し、周波數配列にO(m n)空間を使用します。したがって、空間計算量は O(m * n) です。

このソリューションは、指定された制約內で問題を効率的に処理する必要があります。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上が最初に完全にペイントされた行または列の詳細內容です。詳細については、PHP 中國語 Web サイトの他の関連記事を參照してください。