36 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的个数进行升序表示。 如1,3,7 ，二进制为1,11,111，所以排序结果为1,3,7

问题在于，如何获得1的个数。

根据异或运算 0^1=1 0^0=0

以及Integer.bitCount(i)可以求出异或之后1的个数。 因此，我们可以将当前值i，以及对应二进制异或后1的个数x，存在map中，然后对map按x排序，最后返回i序列。

解答

class Solution {
    public int[] sortByBits(int[] arr) {
        int n=arr.length;
        TreeMap map = new TreeMap();
        for (int value : arr) {
            map.put(value, Integer.bitCount(value ^ 0));
        }
        int[] res = new int[n];

        //这里将map.entrySet()转换成list
        List<Map.Entry<Integer,Integer>> list = new ArrayList<Map.Entry<Integer,Integer>>(map.entrySet());
        //然后通过比较器来实现排序
        //升序排序
        list.sort(Comparator.comparing(Map.Entry::getValue));

        int i=0;
        for(Map.Entry<Integer,Integer> mapping:list){
            res[i]=mapping.getKey();
            i++;
        }
        return res;
        
    }
}

然而，77个实例，只通过了54个。原因不知道。评论区的答案我也看不懂。 贴一下评论区的答案。

class Solution {
    public int[] sortByBits(int[] arr) {
        Integer[] a = new Integer[arr.length];
        for (int i = 0; i < a.length; ++i)
            a[i] = arr[i];
        Arrays.sort(a, Comparator.comparing(i -> Integer.bitCount(i) * 10000 + i));
        for (int i = 0; i < a.length; ++i)
            arr[i] = a[i];
        return arr;
        
    }
}