Given an array of positive integers (possibly with duplicates) such that the numbers have been sorted only by 28 most significant bits. Sort the array completely.
Example 1:
Input: [0, 15, 12, 17, 18, 19, 33, 32]
Output: [0, 12, 15, 17, 18, 19, 32, 33]
Explanation:
The integers in their binary representation are:
0 = 0000 0000 0000 0000 0000 0000 0000 0000
15 = 0000 0000 0000 0000 0000 0000 0000 1111
12 = 0000 0000 0000 0000 0000 0000 0000 1100
17 = 0000 0000 0000 0000 0000 0000 0001 0001
18 = 0000 0000 0000 0000 0000 0000 0001 0010
19 = 0000 0000 0000 0000 0000 0000 0001 0011
33 = 0000 0000 0000 0000 0000 0000 0010 0001
32 = 0000 0000 0000 0000 0000 0000 0010 0000
In sorted order:
0 = 0000 0000 0000 0000 0000 0000 0000 0000
12 = 0000 0000 0000 0000 0000 0000 0000 1100
15 = 0000 0000 0000 0000 0000 0000 0000 1111
17 = 0000 0000 0000 0000 0000 0000 0001 0001
18 = 0000 0000 0000 0000 0000 0000 0001 0010
19 = 0000 0000 0000 0000 0000 0000 0001 0011
32 = 0000 0000 0000 0000 0000 0000 0010 0000
33 = 0000 0000 0000 0000 0000 0000 0010 0001Example 2:
Input: [100207, 100205, 100204, 100206, 100203]
Output: [100203, 100204, 100205, 100206, 100207]
Explanation:
The integers in their binary representation are:
100207 = 0000 0000 0000 0001 1000 0111 0110 1111
100205 = 0000 0000 0000 0001 1000 0111 0110 1101
100204 = 0000 0000 0000 0001 1000 0111 0110 1100
100206 = 0000 0000 0000 0001 1000 0111 0110 1110
100203 = 0000 0000 0000 0001 1000 0111 0110 1011
In sorted order:
100203 = 0000 0000 0000 0001 1000 0111 0110 1011
100204 = 0000 0000 0000 0001 1000 0111 0110 1100
100205 = 0000 0000 0000 0001 1000 0111 0110 1101
100206 = 0000 0000 0000 0001 1000 0111 0110 1110
100207 = 0000 0000 0000 0001 1000 0111 0110 1111Expected O(n) time solution.
Comments (30)