21. Merge Two Queues
Two checkout lanes each hand out numbered tickets in increasing order. At closing time the manager wants a single combined log of all the ticket numbers issued by both lanes, still ordered from smallest to largest. If both lanes issued the same number, both copies must appear in the log.
Write a method mergeSorted that takes the two sorted arrays a and b and returns one sorted array containing every element of both.
Example 1
- Input:
- a = [1,3,5], b = [2,4,6]
- Output:
- [1,2,3,4,5,6]
- Explanation:
Taking the smaller front element each time gives 1, 2, 3, 4, 5, 6.
Example 2
- Input:
- a = [1,1], b = [1,2]
- Output:
- [1,1,1,2]
- Explanation:
Every ticket is kept, including the repeated 1s: [1, 1, 1, 2].
Constraints
1 ≤ a.length, b.length ≤ 1000
-109 ≤ a[i], b[i] ≤ 109
Both a and b are sorted in non-decreasing order
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)
- Space
- O(n + m)