尋找兩個數組的前綴公共數組

2657。找出兩個數組的前綴公共數組

難度：中

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

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

A 和 B 的 A 前綴公共數組 是一個數組 C，使得 C[i] 等於 A 和 B 中索引 i 處或之前出現的數字的計數。

傳回A和B的前綴公共數組。

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

排列。

範例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個整數的排列。

提示：

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

解：

我們可以迭代兩個陣列 A 和 B，同時追蹤兩個陣列中目前索引處或之前出現的數字。由於兩個數組都是同一組數字的排列，因此我們可以利用兩個雜湊集（或數組）來儲存哪些數字出現在兩個數組中的目前索引處或之前。對於每個索引，我們可以計算到目前為止兩個陣列中出現的公共數字。

解決辦法：

1. 使用兩個陣列來追蹤 A 和 B 中直到索引 i 的數字的出現情況。
2. 對於每個索引 i，檢查 A[i] 和 B[i] 之前是否已經見過。如果是這樣，請增加公共計數。
3. 使用頻率數組來追蹤兩個數組中從 1 到 n 的數字的存在。

讓我們用 PHP 實作這個解：2657。找出兩個陣列的前綴公共數組

<?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. 頻率數組：我們維護兩個頻率數組，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 的每個元素以查看它是否常見，從而使該解決方案的時間複雜度呈二次方。考慮到限制 n ≤ 50.
，這是可以接受的

這應該在給定的限制下有效地工作。

聯絡連結

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

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是尋找兩個數組的前綴公共數組的詳細內容。更多資訊請關注PHP中文網其他相關文章！