[LeetCode] 1356. Sort Integers by The Number of 1 Bits

Given an integer array arr. You have to sort the integers in the array in ascending order by the number of 1’s in their binary representation and in case of two or more integers have the same number of 1’s you have to sort them in ascending order.

Return the sorted array.

Example 1:
Input: arr = [0,1,2,3,4,5,6,7,8]
Output: [0,1,2,4,8,3,5,6,7]
Explantion: [0] is the only integer with 0 bits.
[1,2,4,8] all have 1 bit.
[3,5,6] have 2 bits.
[7] has 3 bits.
The sorted array by bits is [0,1,2,4,8,3,5,6,7]

Example 2:
Input: arr = [1024,512,256,128,64,32,16,8,4,2,1]
Output: [1,2,4,8,16,32,64,128,256,512,1024]
Explantion: All integers have 1 bit in the binary representation, you should just sort them in ascending order.

Example 3:
Input: arr = [10000,10000]
Output: [10000,10000]

Example 4:
Input: arr = [2,3,5,7,11,13,17,19]
Output: [2,3,5,17,7,11,13,19]

Example 5:
Input: arr = [10,100,1000,10000]
Output: [10,100,10000,1000]

Constraints:
1 <= arr.length <= 500
0 <= arr[i] <= 10^4

根据数字二进制下 1 的数目排序。

给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。

如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。

请你返回排序后的数组。

思路

题意很简单，对于每个数字，我们计算其二进制表达中的 1 的个数，根据 1 出现的数量多少对数组进行排序。对于两个二进制表达中 1 的数量相同的数字，我们再按照其十进制的表达由大到小排序。

这道题不涉及算法，就是按这个规则实现排序即可。我认为这道题的重点就是让你记住语言里是有自带的 api 帮你快速计算一个二进制数字里面有几个 1。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
    public int[] sortByBits(int[] arr) {
        int n = arr.length;
        Integer[] nums = new Integer[n];
        for (int i = 0; i < n; i++) {
            nums[i] = arr[i];
        }

        Arrays.sort(nums, (a, b) -> Integer.bitCount(a) == Integer.bitCount(b) ? a - b : Integer.bitCount(a) - Integer.bitCount(b));
        for (int i = 0; i < n; i++) {
            arr[i] = nums[i];
        }
        return arr;
    }
}