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

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 サイトの他の関連記事を参照してください。