Skip to content

Latest commit

 

History

History
278 lines (219 loc) · 5.95 KB

README.md

File metadata and controls

278 lines (219 loc) · 5.95 KB
comments difficulty edit_url rating source tags
true
简单
1257
第 20 场双周赛 Q1
位运算
数组
计数
排序

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

English Version

题目描述

给你一个整数数组 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$ 的长度。

Python3

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

Java

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;
    }
}

C++

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        for (int& v : arr) {
            v += __builtin_popcount(v) * 100000;
        }
        sort(arr.begin(), arr.end());
        for (int& v : arr) {
            v %= 100000;
        }
        return arr;
    }
};

Go

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
}

TypeScript

function sortByBits(arr: number[]): number[] {
    const countOnes = (n: number) => {
        let res = 0;
        while (n) {
            n &= n - 1;
            res++;
        }
        return res;
    };
    return arr.sort((a, b) => countOnes(a) - countOnes(b) || a - b);
}

Rust

impl Solution {
    pub fn sort_by_bits(mut arr: Vec<i32>) -> Vec<i32> {
        arr.sort_by(|a, b| {
            let res = a.count_ones().cmp(&b.count_ones());
            if res == std::cmp::Ordering::Equal {
                return a.cmp(&b);
            }
            res
        });
        arr
    }
}

C

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int countOnes(int n) {
    int res = 0;
    while (n) {
        n &= n - 1;
        res++;
    }
    return res;
}

int cmp(const void* _a, const void* _b) {
    int a = *(int*) _a;
    int b = *(int*) _b;
    int res = countOnes(a) - countOnes(b);
    if (res == 0) {
        return a - b;
    }
    return res;
}

int* sortByBits(int* arr, int arrSize, int* returnSize) {
    qsort(arr, arrSize, sizeof(int), cmp);
    *returnSize = arrSize;
    return arr;
}

方法二

Java

class Solution {
    public int[] sortByBits(int[] arr) {
        int n = arr.length;
        Integer[] t = new Integer[n];
        for (int i = 0; i < n; ++i) {
            t[i] = arr[i];
        }
        Arrays.sort(t, (a, b) -> {
            int x = Integer.bitCount(a), y = Integer.bitCount(b);
            return x == y ? a - b : x - y;
        });
        for (int i = 0; i < n; ++i) {
            arr[i] = t[i];
        }
        return arr;
    }
}

C++

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        sort(arr.begin(), arr.end(), [&](auto& a, auto& b) -> bool {
            int x = __builtin_popcount(a), y = __builtin_popcount(b);
            return x < y || (x == y && a < b);
        });
        return arr;
    }
};

Go

func sortByBits(arr []int) []int {
	sort.Slice(arr, func(i, j int) bool {
		a, b := bits.OnesCount(uint(arr[i])), bits.OnesCount(uint(arr[j]))
		return a < b || (a == b && arr[i] < arr[j])
	})
	return arr
}