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

Categories:

题目描述
思路分析
1. 解法一：自定义排序（推荐）
相似题目

题目描述

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

思路分析

解法一：自定义排序（推荐）

核心思路：

以二进制 1 的数量为第一关键字、数值大小为第二关键字排序。

位数可通过 x & (x - 1) 统计。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示数组长度。

空间复杂度：O(n)，用于排序缓存。

import java.util.Arrays;

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

        Arrays.sort(nums, (a, b) -> {
            int ca = countBits(a);
            int cb = countBits(b);
            if (ca != cb) {
                return ca - cb;
            }
            return a - b;
        });

        for (int i = 0; i < nums.length; i++) {
            arr[i] = nums[i];
        }

        return arr;
    }

    private int countBits(int x) {
        int count = 0;
        while (x != 0) {
            x &= x - 1;
            count++;
        }
        return count;
    }
}

import "sort"

func sortByBits(arr []int) []int {
	bits := make(map[int]int)
	countBits := func(x int) int {
		if v, ok := bits[x]; ok {
			return v
		}
		c := 0
		v := x
		for v != 0 {
			v &= v - 1
			c++
		}
		bits[x] = c
		return c
	}

	sort.Slice(arr, func(i, j int) bool {
		bi := countBits(arr[i])
		bj := countBits(arr[j])
		if bi != bj {
			return bi < bj
		}
		return arr[i] < arr[j]
	})

	return arr
}

相似题目

题目	难度	考察点
1356. 根据数字二进制下 1 的数目排序	简单	位运算、排序
191. 位 1 的个数	简单	位运算
338. 比特位计数	简单	位运算
1480. 一维数组的动态和	简单	数组
645. 错误的集合	简单	数组

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/54003873