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.
1import java.util.*;
2
3public
In Java, a HashMap assigns rank to arr2 elements, which is leveraged by the custom comparator during sort execution.
It enables a proper order by first distinguishing presence in arr2 and then by lexicographical placement for arr1's other numbers.