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

難度：中

主題：陣列、雜湊表、位元操作

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

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

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

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

排列。

範(fàn)例1：

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

範(fàn)例2：

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

約束：

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

提示：

考慮保留一個(gè)頻率數(shù)組來(lái)儲(chǔ)存每個(gè)數(shù)字出現(xiàn)的次數(shù)，直到索引 i。
如果一個(gè)數(shù)字出現(xiàn)了兩次，則表示它同時(shí)出現(xiàn)在 A 和 B 中，因?yàn)樗鼈兌际桥帕校栽诖鸢钢屑?1。

解：

我們可以迭代兩個(gè)陣列 A 和 B，同時(shí)追蹤兩個(gè)陣列中目前索引處或之前出現(xiàn)的數(shù)字。由於兩個(gè)數(shù)組都是同一組數(shù)字的排列，因此我們可以利用兩個(gè)雜湊集（或數(shù)組）來(lái)儲(chǔ)存哪些數(shù)字出現(xiàn)在兩個(gè)數(shù)組中的目前索引處或之前。對(duì)於每個(gè)索引，我們可以計(jì)算到目前為止兩個(gè)陣列中出現(xiàn)的公共數(shù)字。

解決辦法：

1. 使用兩個(gè)陣列來(lái)追蹤 A 和 B 中直到索引 i 的數(shù)字的出現(xiàn)情況。
2. 對(duì)於每個(gè)索引 i，檢查 A[i] 和 B[i] 之前是否已經(jīng)見過。如果是這樣，請(qǐng)?jiān)黾庸灿?jì)數(shù)。
3. 使用頻率數(shù)組來(lái)追蹤兩個(gè)數(shù)組中從 1 到 n 的數(shù)字的存在。

讓我們用 PHP 實(shí)作這個(gè)解：2657。找出兩個(gè)陣列的前綴公共數(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ù)組：我們維護(hù)兩個(gè)頻率數(shù)組，freqA 和 freqB，其中每個(gè)索引代表排列中的一個(gè)數(shù)字。
   • 當(dāng)我們?cè)?A[i] 或 B[i] 中遇到數(shù)字時(shí)，我們會(huì)增加頻率數(shù)組中對(duì)應(yīng)的值。
2. 常見計(jì)數(shù)：更新 A[i] 和 B[i] 的頻率數(shù)組後，我們檢查每個(gè)數(shù)字是否出現(xiàn)在兩個(gè)數(shù)組中直至索引 i。如果是這樣，我們?cè)黾?commonCount。
3. 結(jié)果：公共計(jì)數(shù)儲(chǔ)存在每個(gè)索引的結(jié)果陣列中。

演練範(fàn)例：

輸入：

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

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

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

時(shí)間複雜度：

• O(n²⁾：對(duì)於每個(gè)索引i，我們檢查從1 到n 的每個(gè)元素以查看它是否常見，從而使該解決方案的時(shí)間複雜度呈二次方?？紤]到限制 n ≤ 50.
，這是可以接受的

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

聯(lián)絡(luò)連結(jié)

如果您發(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è)數(shù)組的前綴公共數(shù)組的詳細(xì)內(nèi)容。更多資訊請(qǐng)關(guān)注PHP中文網(wǎng)其他相關(guān)文章！