跳转至

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

题目描述

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

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

请你返回排序后的数组。

 

示例 1：

输入：arr = [0,1,2,3,4,5,6,7,8]
输出：[0,1,2,4,8,3,5,6,7]
解释：[0] 是唯一一个有 0 个 1 的数。
[1,2,4,8] 都有 1 个 1 。
[3,5,6] 有 2 个 1 。
[7] 有 3 个 1 。
按照 1 的个数排序得到的结果数组为 [0,1,2,4,8,3,5,6,7]

示例 2：

输入：arr = [1024,512,256,128,64,32,16,8,4,2,1]
输出：[1,2,4,8,16,32,64,128,256,512,1024]
解释：数组中所有整数二进制下都只有 1 个 1 ，所以你需要按照数值大小将它们排序。

示例 3：

输入：arr = [10000,10000]
输出：[10000,10000]

示例 4：

输入：arr = [2,3,5,7,11,13,17,19]
输出：[2,3,5,17,7,11,13,19]

示例 5：

输入：arr = [10,100,1000,10000]
输出：[10,100,10000,1000]

 

提示：

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

解法

方法一：自定义排序

我们将数组 \(arr\) 按照题目要求排序，即按照二进制表示中数字 \(1\) 的数目升序排序，如果存在多个数字二进制中 \(1\) 的数目相同，则必须将它们按照数值大小升序排列。

时间复杂度 \(O(n \times \log n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 为数组 \(arr\) 的长度。

1
2
3
class Solution:
    def sortByBits(self, arr: List[int]) -> List[int]:
        return sorted(arr, key=lambda x: (x.bit_count(), x))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public int[] sortByBits(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; ++i) {
            arr[i] += Integer.bitCount(arr[i]) * 100000;
        }
        Arrays.sort(arr);
        for (int i = 0; i < n; ++i) {
            arr[i] %= 100000;
        }
        return arr;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        for (int& x : arr) {
            x += __builtin_popcount(x) * 100000;
        }
        ranges::sort(arr);
        for (int& x : arr) {
            x %= 100000;
        }
        return arr;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
func sortByBits(arr []int) []int {
    for i, v := range arr {
        arr[i] += bits.OnesCount(uint(v)) * 100000
    }
    sort.Ints(arr)
    for i := range arr {
        arr[i] %= 100000
    }
    return arr
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function sortByBits(arr: number[]): number[] {
    const n = arr.length;

    for (let i = 0; i < n; ++i) {
        arr[i] += bitCount(arr[i]) * 100000;
    }

    arr.sort((a, b) => a - b);

    for (let i = 0; i < n; ++i) {
        arr[i] %= 100000;
    }

    return arr;
}

function bitCount(i: number): number {
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
impl Solution {
    pub fn sort_by_bits(mut arr: Vec<i32>) -> Vec<i32> {
        let n = arr.len();

        for i in 0..n {
            arr[i] += arr[i].count_ones() as i32 * 100000;
        }

        arr.sort();

        for i in 0..n {
            arr[i] %= 100000;
        }

        arr
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
static int bitCount(int x) {
    int cnt = 0;
    while (x) {
        x &= (x - 1);
        ++cnt;
    }
    return cnt;
}

static int cmp(const void* a, const void* b) {
    int x = *(const int*) a;
    int y = *(const int*) b;

    int cx = bitCount(x);
    int cy = bitCount(y);

    if (cx != cy) {
        return cx - cy;
    }
    return x - y;
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* sortByBits(int* arr, int arrSize, int* returnSize) {
    *returnSize = arrSize;

    int* res = (int*) malloc(sizeof(int) * arrSize);
    if (!res) {
        return NULL;
    }

    for (int i = 0; i < arrSize; ++i) {
        res[i] = arr[i];
    }

    qsort(res, arrSize, sizeof(int), cmp);

    return res;
}

评论