题目描述
给你一个整数数组 arr
。请你将数组中的元素按照其二进制表示中数字 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]
输入: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 ,所以你需要按照数值大小将它们排序。
输入:arr = [10000,10000]
输出:[10000,10000]
输入:arr = [2,3,5,7,11,13,17,19]
输出:[2,3,5,17,7,11,13,19]
输入:arr = [10,100,1000,10000]
输出:[10,100,10000,1000]
限制
1 <= arr.length <= 500
0 <= arr[i] <= 10^4
算法1
(直接排序) $O(n \log^2 n)$
- 通过 STL 的
sort
进行排序,比较函数中现场求每两个数二进制 1 的个数。
时间复杂度
- 由于比较函数需要 $O(\log n)$ 的时间,所以总时间复杂度为 $O(n \log^2 n)$。
空间复杂度
- 仅需常数的额外空间。
C++ 代码
class Solution {
public:
vector<int> sortByBits(vector<int>& arr) {
sort(arr.begin(), arr.end(), [](int x, int y) {
int cx = 0, cy = 0;
for (int i = 0; i < 15; i++) {
if (x & (1 << i)) cx++;
if (y & (1 << i)) cy++;
}
if (cx != cy)
return cx < cy;
return x < y;
});
return arr;
}
};
算法2
(预处理后排序) $O(n \log n)$
- 首先计算出每个数字的二进制的 1 的个数,存放在一个数组中。
- 然后排序另一个标号数组,按照标号数组的关系得到最终数组。
时间复杂度
- 预处理的时间复杂度为 $O(n \log n)$。
- 最终排序的时间复杂度也为 $O(n \log n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存放这两个数组。
C++ 代码
class Solution {
public:
vector<int> sortByBits(vector<int>& arr) {
int n = arr.size();
vector<int> a(n), b(n);
for (int i = 0; i < n; i++) {
int x = arr[i], c = 0;
for (int j = 0; j < 14; j++)
if (x & (1 << j)) c++;
a[i] = c;
b[i] = i;
}
sort(b.begin(), b.end(), [&](int i, int j) {
if (a[i] != a[j])
return a[i] < a[j];
return arr[i] < arr[j];
});
for (int i = 0; i < n; i++)
a[i] = arr[b[i]];
return a;
}
};
为什么直接对arr数组而不是对b数组进行排序就会报错(堆溢出)呢 感觉直接在sort函数里面用arr替换b好像逻辑上也没问题呀
这个得看下你的代码了
想问一下大佬,你在两个sort自定义比较函数中,第二个是&,第一个是,我猜可能是因为第二个引用了其他数组。想问一下加不加&的具体原因和方法
可以参考C++11官方手册,Lambda expressions
空 capture
[]
,就是不使用任何外部变量