1122. Relative Sort Array

leetcode easy

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

Task

Даны два массива arr1 и arr2, элементы arr2 уникальны, и все элементы arr2 также присутствуют в arr1.

Отсортируйте элементы arr1 таким образом, чтобы относительный порядок элементов в arr1 был таким же, как в arr2. Элементы, которые не встречаются в arr2, должны быть размещены в конце arr1 в порядке возрастания.

Пример:

Input: arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]

Output: [2,2,2,1,4,3,3,9,6,7,19]

C# solution

matched/original

public class Solution {
    public int[] RelativeSortArray(int[] arr1, int[] arr2) {
        var countMap = new Dictionary<int, int>();
        var remaining = new List<int>();
        var result = new List<int>();
        foreach (var value in arr2) {
            countMap[value] = 0;
        }
        foreach (var value in arr1) {
            if (countMap.ContainsKey(value)) {
                countMap[value]++;
            } else {
                remaining.Add(value);
            }
        }
        remaining.Sort();
        foreach (var value in arr2) {
            for (int i = 0; i < countMap[value]; i++) {
                result.Add(value);
            }
        }
        result.AddRange(remaining);
        return result.ToArray();
    }
}

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>& RelativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        var countMap = new unordered_map<int, int>();
        var remaining = new List<int>();
        var result = new List<int>();
        foreach (var value in arr2) {
            countMap[value] = 0;
        }
        foreach (var value in arr1) {
            if (countMap.count(value)) {
                countMap[value]++;
            } else {
                remaining.push_back(value);
            }
        }
        remaining.Sort();
        foreach (var value in arr2) {
            for (int i = 0; i < countMap[value]; i++) {
                result.push_back(value);
            }
        }
        result.AddRange(remaining);
        return result.ToArray();
    }
}

Java solution

matched/original

class Solution {

    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        Map<Integer, Integer> countMap = new HashMap<>();
        List<Integer> remaining = new ArrayList<>();
        List<Integer> result = new ArrayList<>();

        for (int value : arr2) {
            countMap.put(value, 0);
        }

        for (int value : arr1) {
            if (countMap.containsKey(value)) {
                countMap.put(value, countMap.get(value) + 1);
            } else {
                remaining.add(value);
            }
        }

        Collections.sort(remaining);

        for (int value : arr2) {
            for (int j = 0; j < countMap.get(value); j++) {
                result.add(value);
            }
        }

        result.addAll(remaining);

        return result.stream().mapToInt(Integer::intValue).toArray();
    }
}

JavaScript solution

matched/original

var relativeSortArray = function(arr1, arr2) {
    let countMap = new Map();
    let remaining = [];
    let result = [];

    for (let value of arr2) {
        countMap.set(value, 0);
    }

    for (let value of arr1) {
        if (countMap.has(value)) {
            countMap.set(value, countMap.get(value) + 1);
        } else {
            remaining.push(value);
        }
    }

    remaining.sort((a, b) => a - b);

    for (let value of arr2) {
        let count = countMap.get(value);
        for (let i = 0; i < count; i++) {
            result.push(value);
        }
    }

    return result.concat(remaining);
};

Python solution

matched/original

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        countMap = {value: 0 for value in arr2}
        remaining = []
        result = []

        for value in arr1:
            if value in countMap:
                countMap[value] += 1
            else:
                remaining.append(value)

        remaining.sort()

        for value in arr2:
            result.extend([value] * countMap[value])

        result.extend(remaining)
        return result

Explanation

Algorithm

Инициализация и подсчёт:

Инициализируйте пустой массив result и массив remaining для хранения оставшихся элементов.

Создайте хеш-таблицу countMap для хранения количества вхождений каждого элемента из arr2 в arr1.

Заполнение countMap и remaining:

Пройдитесь по элементам arr1 и если элемент присутствует в countMap, увеличьте его счетчик. Если элемент не присутствует в arr2, добавьте его в remaining.

Формирование результирующего массива:

Пройдитесь по arr2 и добавьте элементы в result в соответствии с их количеством в countMap.

Отсортируйте массив remaining и добавьте его элементы в result.

Верните result в виде массива.

😎