JavaScript / TypeScript / PHP / GO / Python / C / C++ / C# / Java 自定义排序 + 位运算 / 字母哈希映射，求解《1356. 根据数字二进制下 1 的数目排序》
例题
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]
答案
自定义排序 · 位运算
var sortByBits = function(arr) {
return arr.sort((a, b) => count1(a) - count1(b) || a - b)
};
const count1 = n => {
let r = 0
while (n) {
r++
n &= n - 1
}
return r
}自定义排序 · 哈希映射（小写字母）
function sortByBits(arr: number[]): number[] {
const h = new Uint8Array(10001)
for (let i = 1; i <= 10000; i++) h[i] = h[i >> 1] + (i & 1)
return arr.sort((a, b) => h[a] - h[b] || a - b)
};class Solution {
function sortByBits($arr) {
$h = array_fill(0, 10001, 0);
for ($i = 1; $i <= 10000; $i++) $h[$i] = $h[$i >> 1] + ($i & 1);
usort($arr, function($a, $b) use(&$h) {
$t = $h[$a] - $h[$b];
return $t === 0 ? $a > $b : $t;
});
return $arr;
}
}func sortByBits(arr []int) []int {
h := make([]int, 10001)
for i := 1; i <= 10000; i++ {
h[i] = h[i >> 1] + i & 1
}
sort.SliceStable(arr, func(i, j int) bool {
t := h[arr[i]] - h[arr[j]]
if t == 0 {
return arr[i] < arr[j]
}
return t < 0
})
return arr
}class Solution:
def sortByBits(self, arr: List[int]) -> List[int]:
h = [0] * 10001
for i in range(1, 10001): h[i] = h[i >> 1] + (i & 1)
return sorted(arr, key = lambda x : (h[x], x))class Solution {
public int[] sortByBits(int[] arr) {
int n = arr.length;
int[] h = new int[10001];
for (int i = 1; i <= 10000; i++) {
h[i] = h[i >> 1] + (i & 1);
}
Integer[] nums = new Integer[n];
for (int i = 0; i < n; i++) {
nums[i] = arr[i];
}
Arrays.sort(nums, (a, b) -> {
int t = h[a] - h[b];
return t == 0 ? a - b : t;
});
for (int i = 0; i < n; i++) {
arr[i] = nums[i];
}
return arr;
}
}public class Solution {
public int[] SortByBits(int[] arr) {
int[] h = new int[10001];
for (int i = 1; i <= 10000; i++) {
h[i] = h[i >> 1] + (i & 1);
}
Array.Sort(arr, delegate(int a, int b) {
int t = h[a] - h[b];
return t == 0 ? a - b : t;
});
return arr;
}
}int* sortByBits(int* arr, int arrSize, int* returnSize){
int* h = (int *)malloc(sizeof(int) * 10001);
h[0] = 0;
int cmp (const void * a, const void * b) {
int t = h[*(int*)a] - h[*(int*)b];
return t == 0 ? *(int*)a - *(int*)b : t;
}
for (int i = 1; i <= 10000; i++) {
h[i] = h[i >> 1] + (i & 1);
}
qsort(arr, arrSize, sizeof(int), cmp);
*returnSize = arrSize;
return arr;
}class Solution {
public:
vector<int> sortByBits(vector<int>& arr) {
int h[10001];
for (int i = 0; i < 10001; i++) {
h[i] = h[i >> 1] + (i & 1);
}
sort(arr.begin(), arr.end(), [&] (int a, int b) {
int t = h[a] - h[b];
return t == 0 ? a < b : t < 0;
});
return arr;
}
};