解题思路
统计出每个数二进制表示下1的个数,对于相邻两个数如果存在左边大于右边则交换,所有数都进行交换后,判断是否是有序的。
这里知识点:判断一个数的二进制表示有多少1,如下所示。
判断一个数的二进制有几个1
手写
是可以发现规律的,分为 2 n 2^n 2n和不是 2 n 2^n 2n的数,
假设 n u m = 2 1 = 2 num = 2^1 = 2 num=21=2,则 2 1 2^1 21 & (2-1) = 0,即如果num为 2 n 2^n 2n,则num & (num -1) =0,
反之,则num & (num -1)会把最右边的1去掉,知道&后num为0,则执行的次数就是含有的1的个数。
示例:
#include<stdio.h>
int NumberOf1(int n)
{
int count = 0;
if ((n&(n-1)) == 0) return 1;
while (n)
{
n = n & (n - 1);
count++;
}
return count;
}
int main()
{
int n = 0;
scanf("%d", &n);
int res = NumberOf1(n);
printf("%d", res);
return 0;
}
java方式:
import java.util.Scanner;
public class Main {
public static int NumberOf1(int n){
int count = 0;
if ((n&(n-1)) == 0) return 1;
while (n!= 0){
n = n & (n-1);
count ++;
}
return count;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int res = NumberOf1(n);
System.out.println(res);
scanner.close();
}
}
C++中的__builtin_popcount
C++自带的函数库,用于统计数字在二进制下1的个数。
相关题目:1356. 根据数字二进制下 1 的数目排序。
class Solution {
public:
static bool cmp(int& a,int& b)
{
if(__builtin_popcount(a)!=__builtin_popcount(b))
return __builtin_popcount(a)<__builtin_popcount(b);
else
return a<b;
}
vector<int> sortByBits(vector<int>& arr) {
sort(arr.begin(),arr.end(),cmp);
return arr;
}
};
解题思路
如何判断能够经过转换就能变为有序的。
可以将具有相同1的数归位一组,那么遍历数组时就可以将不同的1分为不同的组,单独对组进行维护,不需要单独创建数组存储,而是分别维护即可。
class Solution {
public:
bool canSortArray(vector<int>& nums) {
int lastcnt = 0;
int lastGroupMax = 0;
int curGroupMax = 0;
for (auto & it : nums){
int curCnt = __builtin_popcount(it);
if (curCnt == lastcnt){
// 是当前组,更新最值
curGroupMax = fmax(curGroupMax, it);
}// 不是当前组
else{
lastcnt = curCnt;
lastGroupMax = curGroupMax;
curGroupMax = it;
}
if (it < lastGroupMax){
return false;
}
}
return true;
}
};