211. Follow the Reference
A school lines up its pupils for a photo using a printed guide. The guide lists some shirt numbers in the order they must appear, and each shirt number appears in the guide at most once. Every number in the guide is worn by at least one pupil in the group, but several pupils may wear the same number, and some pupils wear numbers that are not in the guide at all.
Rearrange arr (the shirt numbers of the pupils) so that the numbers from reference come first, in the order of the guide, with every pupil wearing a guided number placed together in that block. All remaining numbers follow after them, sorted in ascending order. Return the rearranged array.
For example, with shirt numbers [5, 5, 2, 8] and the guide [8, 5], the answer is [8, 5, 5, 2].
Example 1
- Input:
- arr = [40,7,7,3,40,9,1,7], reference = [7,40,3]
- Output:
- [7,7,7,40,40,3,1,9]
- Explanation:
Guided numbers first: three 7s, two 40s and one 3. The numbers 1 and 9 are not in the guide, so they follow in ascending order.
Example 2
- Input:
- arr = [5,5,5], reference = [5]
- Output:
- [5,5,5]
- Explanation:
Every pupil wears a guided number, so the order does not change.
Example 3
- Input:
- arr = [9,4,9,1,4], reference = [4]
- Output:
- [4,4,1,9,9]
- Explanation:
Both 4s come first, then the unguided numbers 1, 9, 9 in ascending order.
Constraints
1 ≤ arr.length ≤ 1000
1 ≤ reference.length ≤ arr.length
0 ≤ arr[i], reference[i] ≤ 1000
All values in reference are distinct and each of them occurs in arr.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n + m + V)
- Space
- O(V)