1122. Relative Sort Array
In this problem we are given 2 arrays where the first array contains all the numbers that the second array has but the second array does not contain all. In mathematics we call array1 to be the superset of array2 and array2 to be the subset of array1. And we are being asked to reproduce an array of elements where each number preservers the index found in the array2. That being said, any number that is not in the subset then we will add to the end of the result array.
Approach
. Repeated Numbers
The numbers in the array are not sorted and the numbers are allowed to repeat itself. If we are asked to maintain the order of the numbers found on array 2 then if a number is repeated more than once we should include the number at i + 1 index from the original number. The best thing that comes in mind is using a Hash Table where we can easily record recurrence and store the numbers at O(n) times where n is the length of the array1.
. Preserving the Order
Now that we have our map object we can loop through the length of array2 and at each iteration check if the number at ith index exist in the map. If if exist, enter a inner loop to add the repeated number at i + 1 index from the original number. The order is preserved since we are using the ith number on array2, starting at index 0, as a pivot to the insertion in the result array at the same index of array2.
. Dealing with Remaining Number
Once we inserted the number k times, where k is the number of times the number repeats, we can delete the key from the map. Once we exit the iteration the map will contain only the keys (number) that array2 does not contain. In the 3r iteration we can simply add the keys at k times that correspond to the value in the map. However, since the elements not included in the second array must be sorted, we should store in another array to then sort it in ascending order.
领英推荐
Result
The result should be all the numbers and the remaining numbers added to the end of the result array in ascending order
Time Complexity
The first iteration where we construct the map is O(n) times where n is the length of the first array. The second iteration and verifying if value exist is O(m) where m is the length of the second array. The prototype.has() has O(1) time complexity. The remaining is O(m-n) since is the difference of lengths from both, And finally, the sorting is O(logn).
O(1) + O(n) + O(m) + O(m-n) + O(logn) = O(nlogn)