План курса / Все задачи / Алгоритмы и структуры данных
Общий префикс с учетом кратности
средне
Даны два массива целых чисел nums1 и nums2 одинаковой длины. Для каждого префикса нужно посчитать число общих элементов c учетом кратности.
"С учетом кратности" - это значит, что присутствие одного и того же числа в префиксах считается с учетом наличия дубликатов.
Пример 1:
Ввод: nums1 = [2,2,3,4], nums2 = [3,2,4,2]
Вывод: [0,1,2,4]
0 = [2] и [3] имеют 0 общих элементов
1 = [2,2] и [3,2] имеют 1 общий элемент (2)
2 = [2,2,3] и [3,2,4] имеют 2 общих элемента (2,3)
4 = [2,2,3,4] и [3,2,4,2] имеют 4 общих элемента (2,2,3,4)
(0,1,2,4)
using System.Collections.Generic;
public class Solution {
public static List<int> FindCommonPrefixV2(List<int> nums1, List<int> nums2) {
int n = nums1.Count;
Dictionary<int, int> count1 = new Dictionary<int, int>();
Dictionary<int, int> count2 = new Dictionary<int, int>();
int commonCount = 0;
List<int> result = new List<int>();
for (int i = 0; i < n; i++) {
if (!count1.ContainsKey(nums1[i])) count1[nums1[i]] = 0;
count1[nums1[i]] += 1;
// если после увеличения count1 содержит меньшее или равное значение
// чисел nums1[i], значит +1 общий элемент
if (count1[nums1[i]] <= (count2.ContainsKey(nums1[i]) ? count2[nums1[i]] : 0)) {
commonCount += 1;
}
if (!count2.ContainsKey(nums2[i])) count2[nums2[i]] = 0;
count2[nums2[i]] += 1;
// если после увеличения count2 содержит меньшее или равное значение
// чисел nums2[i], значит +1 общий элемент
if (count2[nums2[i]] <= (count1.ContainsKey(nums2[i]) ? count1[nums2[i]] : 0)) {
commonCount += 1;
}
result.Add(commonCount);
}
return result;
}
}
#include <vector>
#include <unordered_map>
using namespace std;
vector<int> findCommonPrefixV2(vector<int> nums1, vector<int> nums2) {
int n = nums1.size();
unordered_map<int, int> count1;
unordered_map<int, int> count2;
int commonCount = 0;
vector<int> result;
for (int i = 0; i < n; ++i) {
count1[nums1[i]]++;
// если после увеличения count1 содержит меньшее или равное значение
// чисел nums1[i], значит +1 общий элемент
if (count1[nums1[i]] <= count2[nums1[i]]) {
commonCount++;
}
count2[nums2[i]]++;
// если после увеличения count2 содержит меньшее или равное значение
// чисел nums2[i], значит +1 общий элемент
if (count2[nums2[i]] <= count1[nums2[i]]) {
commonCount++;
}
result.push_back(commonCount);
}
return result;
}
package main
func findCommonPrefixV2(nums1 []int, nums2 []int) []int {
n := len(nums1)
count1 := make(map[int]int)
count2 := make(map[int]int)
commonCount := 0
result := make([]int, n)
for i := 0; i < n; i++ {
count1[nums1[i]]++
// если после увеличения count1 содержит меньшее или равное значение
// чисел nums1[i], значит +1 общий элемент
if count1[nums1[i]] <= count2[nums1[i]] {
commonCount++
}
count2[nums2[i]]++
// если после увеличения count2 содержит меньшее или равное значение
// чисел nums2[i], значит +1 общий элемент
if count2[nums2[i]] <= count1[nums2[i]] {
commonCount++
}
result[i] = commonCount
}
return result
}
import java.util.*;
public class Solution {
public List<Integer> findCommonPrefixV2(List<Integer> nums1, List<Integer> nums2) {
int n = nums1.size();
Map<Integer, Integer> count1 = new HashMap<>();
Map<Integer, Integer> count2 = new HashMap<>();
int commonCount = 0;
List<Integer> result = new ArrayList<>();
for (int i = 0; i < n; i++) {
count1.put(nums1.get(i), count1.getOrDefault(nums1.get(i), 0) + 1);
// если после увеличения count1 содержит меньшее или равное значение
// чисел nums1[i], значит +1 общий элемент
if (count1.get(nums1.get(i)) <= count2.getOrDefault(nums1.get(i), 0)) {
commonCount++;
}
count2.put(nums2.get(i), count2.getOrDefault(nums2.get(i), 0) + 1);
// если после увеличения count2 содержит меньшее или равное значение
// чисел nums2[i], значит +1 общий элемент
if (count2.get(nums2.get(i)) <= count1.getOrDefault(nums2.get(i), 0)) {
commonCount++;
}
result.add(commonCount);
}
return result;
}
}
from typing import List
from collections import defaultdict
def find_common_prefix_v2(nums1: List[int], nums2: List[int]) -> List[int]:
n = len(nums1)
count1 = defaultdict(int)
count2 = defaultdict(int)
common_count = 0
result = []
for i in range(n):
count1[nums1[i]] += 1
# если после увеличения count1 содержит меньшее или равное значение
# чисел nums1[i], значит +1 общий элемент
if count1[nums1[i]] <= count2[nums1[i]]:
common_count += 1
count2[nums2[i]] += 1
# если после увеличения count2 содержит меньшее или равное значение
# чисел nums2[i], значит +1 общий элемент
if count2[nums2[i]] <= count1[nums2[i]]:
common_count += 1
result.append(common_count)
return result
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @returns {number[]}
*/
export function findCommonPrefixV2(nums1, nums2) {
const n = nums1.length;
const count1 = {};
const count2 = {};
let commonCount = 0;
const result = [];
for (let i = 0; i < n; i++) {
// Увеличиваем счетчик для nums1[i]
if (count1[nums1[i]] !== undefined) {
count1[nums1[i]] += 1;
} else {
count1[nums1[i]] = 1;
}
// Если после увеличения count1 содержит меньшее или равное значение чисел nums1[i], значим +1 общий элемент
if (count1[nums1[i]] <= (count2[nums1[i]] || 0)) {
commonCount += 1;
}
// Увеличиваем счетчик для nums2[i]
if (count2[nums2[i]] !== undefined) {
count2[nums2[i]] += 1;
} else {
count2[nums2[i]] = 1;
}
// Если после увеличения count2 содержит меньшее или равное значение чисел nums2[i], значим +1 общий элемент
if (count2[nums2[i]] <= (count1[nums2[i]] || 0)) {
commonCount += 1;
}
result.push(commonCount);
}
return result;
}