2657。查找兩個數(shù)組的前綴公共數(shù)組

難度：中等

主題：數(shù)組、哈希表、位操作

給你兩個0索引長度為n的整數(shù)排列A和B。

A 和 B 的 A 前綴公共數(shù)組 是一個數(shù)組 C，使得 C[i] 等于 A 和 B 中索引 i 處或之前出現(xiàn)的數(shù)字的計數(shù)。

返回A和B的前綴公共數(shù)組。

如果 n 個整數(shù)的序列包含從 1 到 n 的所有整數(shù)恰好一次，則該序列稱為

排列。

示例1：

• 輸入： A = [1,3,2,4], B = [3,1,2,4]
• 輸出： [0,2,3,4]
• 解釋： 當(dāng) i = 0 時：沒有公共數(shù)，因此 C[0] = 0。
  當(dāng) i = 1 時：1 和 3 在 A 和 B 中很常見，因此 C[1] = 2。
  當(dāng) i = 2 時：1、2 和 3 在 A 和 B 中很常見，因此 C[2] = 3。
  當(dāng) i = 3 時：1、2、3 和 4 在 A 和 B 中很常見，因此 C[3] = 4。

示例2：

• 輸入： A = [2,3,1], B = [3,1,2]
• 輸出： [0,1,3]
• 解釋： 當(dāng) i = 0 時：沒有公共數(shù)，因此 C[0] = 0。
  當(dāng) i = 1 時：A 和 B 中只有 3 是常見的，因此 C[1] = 1。
  當(dāng) i = 2 時：1、2 和 3 在 A 和 B 中很常見，因此 C[2] = 3。

約束：

1 1 保證A和B都是n個整數(shù)的排列。

提示：

考慮保留一個頻率數(shù)組來存儲每個數(shù)字出現(xiàn)的次數(shù)，直到索引 i。
如果一個數(shù)字出現(xiàn)了兩次，則意味著它同時出現(xiàn)在 A 和 B 中，因為它們都是排列，所以在答案中加 1。

解決方案：

我們可以迭代兩個數(shù)組 A 和 B，同時跟蹤兩個數(shù)組中當(dāng)前索引處或之前出現(xiàn)的數(shù)字。由于兩個數(shù)組都是同一組數(shù)字的排列，因此我們可以利用兩個哈希集（或數(shù)組）來存儲哪些數(shù)字出現(xiàn)在兩個數(shù)組中的當(dāng)前索引處或之前。對于每個索引，我們可以計算到目前為止兩個數(shù)組中出現(xiàn)的公共數(shù)字。

解決辦法：

1. 使用兩個數(shù)組來跟蹤 A 和 B 中直到索引 i 的數(shù)字的出現(xiàn)情況。
2. 對于每個索引 i，檢查 A[i] 和 B[i] 之前是否已經(jīng)見過。如果是這樣，請增加公共計數(shù)。
3. 使用頻率數(shù)組來跟蹤兩個數(shù)組中從 1 到 n 的數(shù)字的存在情況。

讓我們用 PHP 實現(xiàn)這個解決方案：2657。查找兩個數(shù)組的前綴公共數(shù)組

<?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. 頻率數(shù)組：我們維護兩個頻率數(shù)組，freqA 和 freqB，其中每個索引代表排列中的一個數(shù)字。
   • 當(dāng)我們在 A[i] 或 B[i] 中遇到數(shù)字時，我們會增加頻率數(shù)組中對應(yīng)的值。
2. 常見計數(shù)：更新 A[i] 和 B[i] 的頻率數(shù)組后，我們檢查每個數(shù)字是否出現(xiàn)在兩個數(shù)組中直至索引 i。如果是這樣，我們增加 commonCount。
3. 結(jié)果：公共計數(shù)存儲在每個索引的結(jié)果數(shù)組中。

演練示例：

輸入：

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

• 當(dāng) i = 0 時：還沒有公共數(shù) → C[0] = 0
• 當(dāng) i = 1 時：數(shù)字 1 和 3 是公共的 → C[1] = 2
• 當(dāng) i = 2 時：數(shù)字 1、2 和 3 是常見的 → C[2] = 3
• 在 i = 3 時：數(shù)字 1、2、3 和 4 是常見的 → C[3] = 4

輸出：[0,2,3,4]

時間復(fù)雜度：

• O(n²⁾：對于每個索引 i，我們檢查從 1 到 n 的每個元素以查看它是否常見，從而使該解決方案的時間復(fù)雜度呈二次方?？紤]到約束 n ≤ 50.
，這是可以接受的

這應(yīng)該在給定的約束下有效地工作。

聯(lián)系鏈接

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

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

• 領(lǐng)英
• GitHub

以上是查找兩個數(shù)組的前綴公共數(shù)組的詳細(xì)內(nèi)容。更多信息請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！