Formatted question description: https://leetcode.ca/all/1122.html
1122. Relative Sort Array (Easy)
Given two arrays arr1
and arr2
, the elements of arr2
are distinct, and all elements in arr2
are also in arr1
.
Sort the elements of arr1
such that the relative ordering of items in arr1
are the same as in arr2
. Elements that don't appear in arr2
should be placed at the end of arr1
in ascending order.
Example 1:
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]
Constraints:
1 <= arr1.length, arr2.length <= 1000
0 <= arr1[i], arr2[i] <= 1000
- All the elements of
arr2
are distinct. - Each
arr2[i]
is inarr1
.
Solution 1.
// OJ: https://leetcode.com/problems/relative-sort-array/
// Time: O(AlogA)
// Space: O(B)
class Solution {
public:
vector<int> relativeSortArray(vector<int>& A, vector<int>& B) {
unordered_map<int, int> m;
for (int i = 0; i < B.size(); ++i) m[B[i]] = i;
sort(begin(A), end(A), [&](int a, int b) {
if (m.count(a) && m.count(b)) return m[a] < m[b];
if (m.count(a) == 0 && m.count(b) == 0) return a < b;
return m.count(a) > 0;
});
return A;
}
};
Solution 2.
// OJ: https://leetcode.com/problems/relative-sort-array/
// Time: O(A + B)
// Space: O(max(A, B))
class Solution {
public:
vector<int> relativeSortArray(vector<int>& A, vector<int>& B) {
int cnt[1001] = {};
vector<int> ans;
for (int n : A) cnt[n]++;
for (int n : B) {
for (int i = 0; i < cnt[n]; ++i) ans.push_back(n);
cnt[n] = 0;
}
for (int i = 0; i <= 1000; ++i) {
for (int j = 0; j < cnt[i]; ++j) ans.push_back(i);
}
return ans;
}
};
Java
class Solution {
public int[] relativeSortArray(int[] arr1, int[] arr2) {
Map<Integer, Integer> orderMap = new HashMap<Integer, Integer>();
int length1 = arr1.length, length2 = arr2.length;
for (int i = 0; i < length2; i++) {
int num = arr2[i];
orderMap.put(num, i);
}
for (int i = 1; i < length1; i++) {
int num = arr1[i];
int order = orderMap.getOrDefault(num, Integer.MAX_VALUE);
int insertIndex = -1;
for (int j = i - 1; j >= 0; j--) {
int curOrder = orderMap.getOrDefault(arr1[j], Integer.MAX_VALUE);
if (curOrder < order || curOrder == order && arr1[j] < num) {
insertIndex = j;
break;
}
arr1[j + 1] = arr1[j];
}
insertIndex++;
arr1[insertIndex] = num;
}
return arr1;
}
}