2657. Find the Prefix Common Array of Two Arrays

Problem

You are given two 0-indexed integer permutations A and B of length n.

A prefix common array of A and B is an array C such that C[i] is equal to the count of numbers that are present at or before the index i in both A and B.

Return the prefix common array of A and B.

A sequence of n integers is called a permutation if it contains all integers from 1 to n exactly once.

https://leetcode.com/problems/find-the-prefix-common-array-of-two-arrays/

Example 1:

Input: A = [1,3,2,4], B = [3,1,2,4]
Output: [0,2,3,4]
Explanation: At i = 0: no number is common, so C[0] = 0.
At i = 1: 1 and 3 are common in A and B, so C[1] = 2.
At i = 2: 1, 2, and 3 are common in A and B, so C[2] = 3.
At i = 3: 1, 2, 3, and 4 are common in A and B, so C[3] = 4.

Example 2:

Input: A = [2,3,1], B = [3,1,2]
Output: [0,1,3]
Explanation: At i = 0: no number is common, so C[0] = 0.
At i = 1: only 3 is common in A and B, so C[1] = 1.
At i = 2: 1, 2, and 3 are common in A and B, so C[2] = 3.

Constraints:

• 1 <= A.length == B.length == n <= 50
• 1 <= A[i], B[i] <= n
• It is guaranteed that A and B are both a permutation of n integers.

Test Cases

1
2

class Solution:
    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:

1
2
3
4
5
6
7
8
9
10
11
12

import pytest

from solution import Solution


@pytest.mark.parametrize('a, b, expected', [
    ([1,3,2,4], [3,1,2,4], [0,2,3,4]),
    ([2,3,1], [3,1,2], [0,1,3]),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, a, b, expected):
    assert sol.findThePrefixCommonArray(a, b) == expected

Thoughts

因为 A 和 B 都是 1 到 n 的排列，所以 1 到 n 的每一个数字在 A 和 B 中都分别刚好有且只有一次，A 和 B 一起看的话则是刚好有且只有两次。

从左到右同时遍历 A 和 B，对见到的数字计数，如果计数值为 2 说明此数字在 A 和 B 的前缀子数组中都出现过。

时间复杂度 O(n)，空间复杂度 O(n)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def findThePrefixCommonArray(self, A: list[int], B: list[int]) -> list[int]:
        counts = [0] * (len(A) + 1)
        res = []
        common = 0
        for pair in zip(A, B):
            for num in pair:
                counts[num] += 1
                if counts[num] == 2:
                    common += 1

            res.append(common)

        return res

许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章