1213. Intersection of Three Sorted Arrays

leetcode easy

#array#csharp#easy#hash-table#leetcode#sort#tree

Task

Даны три целочисленных массива arr1, arr2 и arr3, отсортированных в строго возрастающем порядке. Верните отсортированный массив, содержащий только те целые числа, которые присутствуют во всех трех массивах.

Пример:

Input: arr1 = [1,2,3,4,5], arr2 = [1,2,5,7,9], arr3 = [1,3,4,5,8]

Output: [1,5]

Explanation: Only 1 and 5 appeared in the three arrays.

C# solution

matched/original

public class Solution {
    public IList<int> ArraysIntersection(int[] arr1, int[] arr2, int[] arr3) {
        SortedDictionary<int, int> counter = new SortedDictionary<int, int>();
        foreach (int e in arr1) counter[e] = counter.GetValueOrDefault(e, 0) + 1;
        foreach (int e in arr2) counter[e] = counter.GetValueOrDefault(e, 0) + 1;
        foreach (int e in arr3) counter[e] = counter.GetValueOrDefault(e, 0) + 1;
        List<int> ans = new List<int>();
        foreach (var entry in counter) {
            if (entry.Value == 3) ans.Add(entry.Key);
        }
        return ans;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<int> ArraysIntersection(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) {
        SortedDictionary<int, int> counter = new SortedDictionary<int, int>();
        foreach (int e in arr1) counter[e] = counter.GetValueOrDefault(e, 0) + 1;
        foreach (int e in arr2) counter[e] = counter.GetValueOrDefault(e, 0) + 1;
        foreach (int e in arr3) counter[e] = counter.GetValueOrDefault(e, 0) + 1;
        List<int> ans = new List<int>();
        foreach (var entry in counter) {
            if (entry.Value == 3) ans.push_back(entry.Key);
        }
        return ans;
    }
}

Java solution

matched/original

class Solution {
    public List<Integer> arraysIntersection(int[] arr1, int[] arr2, int[] arr3) {
        List<Integer> ans = new ArrayList<>();

        Map<Integer, Integer> counter = new TreeMap<>();

        for (Integer e: arr1) {
            counter.put(e, counter.getOrDefault(e, 0) + 1);
        }
        for (Integer e: arr2) {
            counter.put(e, counter.getOrDefault(e, 0) + 1);
        }
        for (Integer e: arr3) {
            counter.put(e, counter.getOrDefault(e, 0) + 1);
        }

        for (Integer item: counter.keySet()) {
            if (counter.get(item) == 3) {
                ans.add(item);
            }
        }
        return ans;

    }
}

JavaScript solution

matched/original

class Solution {
    arraysIntersection(arr1, arr2, arr3) {
        const counter = new Map();
        
        for (const e of arr1) counter.set(e, (counter.get(e) || 0) + 1);
        for (const e of arr2) counter.set(e, (counter.get(e) || 0) + 1);
        for (const e of arr3) counter.set(e, (counter.get(e) || 0) + 1);

        const ans = [];
        for (const [key, value] of counter) {
            if (value === 3) ans.push(key);
        }

        return ans;
    }
}

Python solution

matched/original

class Solution:
    def arraysIntersection(self, arr1, arr2, arr3):
        from collections import Counter

        counter = Counter(arr1) + Counter(arr2) + Counter(arr3)
        return [num for num, freq in counter.items() if freq == 3]

Go solution

matched/original

func arraysIntersection(arr1 []int, arr2 []int, arr3 []int) []int {
    counter := make(map[int]int)
    
    for _, e := range arr1 {
        counter[e]++
    }
    for _, e := range arr2 {
        counter[e]++
    }
    for _, e := range arr3 {
        counter[e]++
    }

    var ans []int
    for k, v := range counter {
        if v == 3 {
            ans = append(ans, k)
        }
    }
    
    sort.Ints(ans)
    return ans
}

Explanation

Algorithm

Инициализируйте counter как TreeMap для записи чисел, которые появляются в трех массивах, и количество их появлений.

Пройдитесь по массивам arr1, arr2 и arr3, чтобы посчитать частоты появления элементов.

Итерация через counter, чтобы найти числа, которые появляются три раза, и вернуть их в виде отсортированного массива.

😎