200. Sort by Set Bits
Each non-negative integer has a binary form, and the number of 1 digits in it is its set-bit count. For example, 13 is 1101 in binary, so its set-bit count is 3, and 0 has a count of 0.
Rearrange nums so the numbers with fewer set bits come first. Numbers with the same set-bit count are ordered by their value, smallest first. Return the rearranged array; the input has to stay readable, but you may sort a copy.
Example 1
- Input:
- nums = [7,1,6,2,12]
- Output:
- [1,2,6,12,7]
- Explanation:
Set-bit counts are 7:3, 1:1, 6:2, 2:1, 12:2. Sorted by count then value: 1, 2 (count 1), 6, 12 (count 2), 7 (count 3).
Example 2
- Input:
- nums = [0,8,3]
- Output:
- [0,8,3]
- Explanation:
0 has no set bits, 8 (1000) has one and 3 (11) has two.
Example 3
- Input:
- nums = [5,3,6]
- Output:
- [3,5,6]
- Explanation:
All three have exactly two set bits, so they are ordered by value.
Constraints
1 ≤ nums.length ≤ 105
0 ≤ nums[i] ≤ 109
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 log n)
- Space
- O(n)