05 August 2008
给一个整数array，按照二进制中1的数量从低到高进行排序
bit[i] = bit[i»1] + (i & 1)
时间复杂度：O(nlogn)，其中 n 为整数数组 arr 的长度。
空间复杂度：O(n)，其中 n 为整数数组 arr 的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public int[] sortByBits(int[] arr) {
List<Integer> list = new ArrayList<Integer>();
for (int x : arr) {
list.add(x);
}
int[] bit = new int[10001];
for (int i = 1; i <= 10000; ++i) {
bit[i] = bit[i >> 1] + (i & 1);
}
list.sort((x, y) -> {
if (bit[x] != bit[y]) {
return bit[x] - bit[y];
} else {
return x - y;
}
});
for (int i = 0; i < arr.length; ++i) {
arr[i] = list.get(i);
}
return arr;
}
}
循环并使用 Integer.bitCount 计算数字中1的个数，乘以10000000（题目中不会大于 10^4）然后加上原数字，放入数组 map 中，并对 map 进行排序，最后 % 10000000 获取原来的数组，填充到原数组返回即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public int[] sortByBits(int[] arr) {
int[] map = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
map[i] = Integer.bitCount(arr[i]) * 10000000 + arr[i];
}
Arrays.sort(map);
for (int i = 0; i < map.length; i++) {
map[i] = map[i] % 10000000;
}
return map;
}
}