План курса / Все задачи / Алгоритмы и структуры данных

Общий префикс двух массивов

средне

# решено

Даны два целочисленных массива nums1 и nums2 длины n. Оба массива содержат только числа от 1 до n включительно, при этом каждое число обязательно встречается ровно один раз в каждом из массивов.

Нужно найти общий префиксный массив для nums1 и nums2.

Префиксный массив nums1иnums2— это массив nums3, такой что nums3[i] равен количеству чисел, которые присутствуют на индексе i или до него как в nums1, так и в nums2.

Пример 1:

Ввод: nums1=[2,1,3,4,5], nums2=[3,1,2,5,4]
Вывод: [0,1,3,3,5]
Объяснение:
0 = [2] и [3] имеют 0 общих элементов
1 = [2,1] и [3,1] имеют 1 общий элемент (1)
3 = [2,1,3] и [3,1,2] имеют 3 общих элемента (1,2,3)
3 = [2,1,3,4] и [3,1,2,5] имеют 3 общих элемента (1,2,3)
5 = [2,1,3,4,5] и [3,1,2,5,4] имеют 5 общих элементов (1,2,3,4,5)

Пример 2:

Ввод: nums1=[1,2,3], nums2=[1,2,3]
Вывод: [1,2,3]

Ограничения:

len(nums1) = len(nums2)
len(nums1), len(nums2) >= 1

public class Solution
{
    public static List<int> FindCommonPrefix(List<int> nums1, List<int> nums2)
    {
        var result = new List<int>();
        var frequency = new int[nums1.Count + 1];

        int common = 0;
        for (int i = 0; i < nums1.Count; i++)
        {
            frequency[nums1[i]]++;
            frequency[nums2[i]]++;

            // если общий элемент, то +1 к общим элементам на префиксе
            if (nums1[i] == nums2[i])
            {
                common++;
                result.Add(common);
                continue;
            }

            // если до этого уже встречали nums1[i], то +1
            if (frequency[nums1[i]] == 2)
            {
                common++;
            }

            // если до этого уже встречали nums2[i], то +1
            if (frequency[nums2[i]] == 2)
            {
                common++;
            }

            result.Add(common);
        }
        
        return result;
    }
}

#include <vector>

using namespace std;

vector<int> findCommonPrefix(const vector<int>& nums1, const vector<int>& nums2) {
    vector<int> result;
    vector<int> frequency(nums1.size() + 1, 0);

    int common = 0;
    for (size_t i = 0; i < nums1.size(); i++) {
        frequency[nums1[i]]++;
        frequency[nums2[i]]++;

        // если общий элемент, то +1 к общим элементам на префиксе
        if (nums1[i] == nums2[i]) {
            common++;
            result.push_back(common);
            continue;
        }

        // если до этого уже встречали nums1[i], то +1
        if (frequency[nums1[i]] == 2) {
            common++;
        }
        // если до этого уже встречали nums2[i], то +1
        if (frequency[nums2[i]] == 2) {
            common++;
        }

        result.push_back(common);
    }
    return result;
}

package main

func findCommonPrefix(nums1 []int, nums2 []int) []int {
    result := make([]int, len(nums1))
    frequency := make([]int, len(nums1)+1)

    common := 0
    for i := 0; i < len(nums1); i++ {
        frequency[nums1[i]]++
        frequency[nums2[i]]++

        // если общий элемент, то +1 к общим элементам на префиксе
        if nums1[i] == nums2[i] {
            common++
            result[i] = common
            continue
        }

        // если до этого уже встречали nums1[i], то +1
        if frequency[nums1[i]] == 2 {
            common++
        }
        // если до этого уже встречали nums2[i], то +1
        if frequency[nums2[i]] == 2 {
            common++
        }

        result[i] = common
    }
    return result
}

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<Integer> findCommonPrefix(List<Integer> nums1, List<Integer> nums2) {
        List<Integer> result = new ArrayList<>();
        int[] frequency = new int[nums1.size() + 1];

        int common = 0;
        for (int i = 0; i < nums1.size(); i++) {
            frequency[nums1.get(i)]++;
            frequency[nums2.get(i)]++;

            // если общий элемент, то +1 к общим элементам на префиксе
            if (nums1.get(i).equals(nums2.get(i))) {
                common++;
                result.add(common);
                continue;
            }

            // если до этого уже встречали nums1[i], то +1
            if (frequency[nums1.get(i)] == 2) {
                common++;
            }
            // если до этого уже встречали nums2[i], то +1
            if (frequency[nums2.get(i)] == 2) {
                common++;
            }

            result.add(common);
        }
        return result;
    }
}

from typing import *

def find_common_prefix(nums1: List[int], nums2: List[int]) -> List[int]:
    result = []
    frequency = [0] * (len(nums1) + 1)

    common = 0
    for i in range(len(nums1)):
        frequency[nums1[i]] += 1
        frequency[nums2[i]] += 1

        # если общий элемент, то +1 к общим элементам на префиксе
        if nums1[i] == nums2[i]:
            common += 1
            result.append(common)
            continue

        # если до этого уже встречали nums1[i], то +1
        if frequency[nums1[i]] == 2:
            common += 1
        # если до этого уже встречали nums2[i], то +1
        if frequency[nums2[i]] == 2:
            common += 1

        result.append(common)
    return result

export function findCommonPrefix(nums1, nums2) {
    const result = [];
    const frequency = new Array(nums1.length + 1).fill(0);

    let common = 0;
    for (let i = 0; i < nums1.length; i++) {
        frequency[nums1[i]] += 1;
        frequency[nums2[i]] += 1;

        // если общий элемент, то +1 к общим элементам на префиксе
        if (nums1[i] === nums2[i]) {
            common += 1;
            result.push(common);
            continue;
        }

        // если до этого уже встречали nums1[i], то +1
        if (frequency[nums1[i]] === 2) {
            common += 1;
        }

        // если до этого уже встречали nums2[i], то +1
        if (frequency[nums2[i]] === 2) {
            common += 1;
        }

        result.push(common);
    }
    return result;
}

Оценка сложности

Время: O(n), где n - длина массива nums1 и nums2
Память: O(n), где n - длина массива nums1 и nums2