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.
1def relative_sort_array(arr1, arr2):
2 count = {x: 0 for x in arr2}
3 others = []
4 for number in arr1:
5 if number in count:
6 count[number] += 1
7 else:
8 others.append(number)
9 result = []
10 for number in arr2:
11 result.extend([number] * count[number])
12 return result + sorted(others)
13
14# Example usage
15arr1 = [2,3,1,3,2,4,6,7,9,2,19]
16arr2 = [2,1,4,3,9,6]
17print(relative_sort_array(arr1, arr2)) # Output: [2, 2, 2, 1, 4, 3, 3, 9, 6, 7, 19]This code creates a dictionary to count occurrences of elements present in arr2 and compiles a list of elements that are only in arr1.
Firstly, it iterates over arr1 to populate the dictionary and the extra elements list.
The function then iterates over arr2 and appends each number to the result list based on the count recorded in the dictionary.
Finally, the function appends the sorted extra elements to the result.
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.