Sponsored
Sponsored
This approach uses a hash map (or dictionary) to count the occurrences of each element in arr1. Then, it constructs a new listby first adding elements in the order they appear in arr2 based on their count, and then adding remaining elements in sorted order.
Time Complexity: O(n log n), dominated by the sorting of extra elements not in arr2.
Space Complexity: O(n), primarily due to the dictionary and list of extra elements.
1function relativeSortArray(arr1, arr2) {
2 const countMap = new Map();
3 const others = [];
4 arr2.forEach(num => countMap.set(num, 0));
5 arr1.forEach(num => {
6 if (countMap.has(num)) {
7 countMap.set(num, countMap.get(num) + 1);
8 } else {
9 others.push(num);
10 }
11 });
12 const result = [];
13 arr2.forEach(num => {
14 result.push(...Array(countMap.get(num)).fill(num));
15 });
16 return result.concat(others.sort((a, b) => a - b));
17}
18
19// Example usage
20console.log(relativeSortArray([2,3,1,3,2,4,6,7,9,2,19], [2,1,4,3,9,6]));
21// Output: [2, 2, 2, 1, 4, 3, 3, 9, 6, 7, 19]The JavaScript function uses a map to count each arr2 element found in arr1. Non-arr2 elements are stored separately.
We iterate over arr2, assembling a result array that replicates each arr2 element the number of times stored in our map, before appending sorted non-arr2 members.
Utilize a custom comparator function to sort arr1 according to the order defined in arr2, with arr1 elements not in arr2 sorted at the end.
Time Complexity: O(n log n), determined by the sort operation.
Space Complexity: O(n) for the rank map.
1#include <vector>
2#include <unordered_map>
3#include <algorithm>
4
5std::vector<int> relativeSortArray(std::vector<int>& arr1, std::vector<int>& arr2) {
6 std::unordered_map<int, int> rank;
for (int i = 0; i < arr2.size(); ++i) {
rank[arr2[i]] = i;
}
std::sort(arr1.begin(), arr1.end(), [&rank](int x, int y) {
if (rank.count(x) && rank.count(y))
return rank[x] < rank[y];
if (rank.count(x))
return true;
if (rank.count(y))
return false;
return x < y;
});
return arr1;
}
// Example usage:
// std::vector<int> arr1 = {2,3,1,3,2,4,6,7,9,2,19};
// std::vector<int> arr2 = {2,1,4,3,9,6};
// std::vector<int> output = relativeSortArray(arr1, arr2);The C++ solution employs an unordered_map to assign a rank based on the position of each element in arr2.
Using a lambda function in its custom comparator, this mapping enables arr1 to be reordered according to where each element appears in arr2, with non-mappable (extra) numbers sorted naturally afterward.