2 つの配列の共通のプレフィックス配列を見つける

2657。 2 つの配列のプレフィックス共通配列を検索

難易度: 中

トピック: 配列、ハッシュ テーブル、ビット操作

長さ n の 2 つの 0 インデックス付き 整数順列 A と B が与えられます。

A と B の プレフィックス共通配列 は、C[i] が A と B の両方のインデックス i またはその前に存在する数値のカウントに等しい配列 C です。

A と B の プレフィックス共通配列を 返します。

n 個の整数のシーケンスに 1 から n までのすべての整数が 1 回だけ含まれている場合、そのシーケンスは 順列 と呼ばれます。

例 1:

• 入力: A = [1,3,2,4]、B = [3,1,2,4]
• 出力: [0,2,3,4]
• 説明: i = 0 の場合: 共通の数値がないため、C[0] = 0 になります。
  • i = 1 の場合: 1 と 3 は A と B で共通なので、C[1] = 2 となります。
  • i = 2 の場合: 1、2、3 は A と B で共通なので、C[2] = 3 となります。
  • i = 3 の場合: 1、2、3、4 は A と B で共通なので、C[3] = 4 となります。

例 2:

• 入力: A = [2,3,1]、B = [3,1,2]
• 出力: [0,1,3]
• 説明: i = 0 の場合: 共通の数値がないため、C[0] = 0 になります。
  • i = 1 の場合: A と B で共通なのは 3 だけなので、C[1] = 1。
  • i = 2 の場合: 1、2、3 は A と B で共通なので、C[2] = 3 となります。

制約:

• 1
• 1
• A と B はどちらも n 個の整数の順列であることが保証されています。

ヒント:

1. インデックス i までの各数値の出現回数を格納する頻度配列を保持することを検討してください。
2. ある数字が 2 回出現した場合は、A と B の両方で出現したことを意味します。どちらも順列なので、答えに 1 を加えます。

解決策:

両方の配列の現在のインデックスまたはその前に発生した数値を追跡しながら、2 つの配列 A と B を反復処理できます。両方の配列は同じ数値セットの順列であるため、2 つのハッシュ セット (または配列) を利用して、両方の配列の現在のインデックスまたはその前にどの数値が出現したかを格納できます。各インデックスについて、その時点までに両方の配列に出現した共通の数値を数えることができます。

解決策のアプローチ:

1. 2 つの配列を使用して、インデックス i までの A と B の両方の数値の出現を追跡します。
2. 各インデックス i について、A[i] と B[i] の両方が以前に見られたかどうかを確認します。その場合、共通数を増やします。
3. 頻度配列を使用して、両方の配列内の 1 から n までの数値の存在を追跡します。

このソリューションを PHP で実装してみましょう: 2657。 2 つの配列のプレフィックス共通配列を検索

<?php /**
 * @param Integer[] $A
 * @param Integer[] $B
 * @return Integer[]
 */
function findThePrefixCommonArray($A, $B) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$A = [1, 3, 2, 4];
$B = [3, 1, 2, 4];
print_r(findThePrefixCommonArray($A, $B)); // Output: [0, 2, 3, 4]

$A = [2, 3, 1];
$B = [3, 1, 2];
print_r(findThePrefixCommonArray($A, $B)); // Output: [0, 1, 3]
?>

説明：

1. 周波数配列: 2 つの周波数配列 freqA と freqB を維持します。各インデックスは順列内の数値を表します。
   • A[i] または B[i] に数値が現れると、周波数配列内の対応する値が増加します。
2. 共通カウント: A[i] と B[i] の両方の周波数配列を更新した後、各数値がインデックス i までの両方の配列に出現したかどうかを確認します。そうであれば、commonCount を増やします。
3. 結果: 共通カウントは各インデックスの結果配列に保存されます。

チュートリアルの例:

入力用:

$A = [1, 3, 2, 4];
$B = [3, 1, 2, 4];

• i = 0 の場合: 共通の数値はまだありません → C[0] = 0
• i = 1 の場合: 数値 1 と 3 は共通 → C[1] = 2
• i = 2 の場合: 数値 1、2、3 は共通 → C[2] = 3
• i = 3 の場合: 数値 1、2、3、4 は共通 → C[3] = 4

出力: [0, 2, 3, 4]

時間計算量:

• O(n²⁾: 各インデックス i について、1 から n までのすべての要素をチェックして共通かどうかを確認し、この解の時間計算量は 2 次になります。 n ≤ 50.
という制約を考慮すると、これは許容されます。

これは、指定された制約内で効果的に機能するはずです。

連絡先リンク

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

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

• LinkedIn
• GitHub

以上が2 つの配列の共通のプレフィックス配列を見つけるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。