Mario大叔叔👨 
获赞
5
粉丝
0
关注
1
看过 TA
0
华南理工大学 2021 C++ IP属地：未知暂未填写个人简介
辣条咸鱼王：自测了用例，都能过
查看图片 2020-04-09 01:22
华南理工大学 C++ 
hurley：我把这个算法称为找♂0算法，从定义出发的思路：
1：MAX情况，FFFF是最大的二进制数
2：对于任何一个二进制数，比较大小的条件：
a) 如果所有位都相等，那么两个数相等
b) 从左向右两个数间第一个不同的位中，是1的那个数更大
所以，对于两个不同的数，只要最高不同位是1，那么后面的数是多少都无所谓。
因此对数组从左到右循环，找到第一个为0的位，努力让这个位变成1，变成1的方法是：看这个位的后一位是否是0，如果是0则00->10变化成功，如果是1则再看1后是不是0，如果是0则010->001->101变化成功，以此类推，当访问到末尾时还找不到能提供0的对，那么算法无能为力，可以返回了。
以下是pseudocode
bool move(int arr[],int start,int size){
if(start==size) false;
if(arr[start+1]!=0){
move(arr,start+1,size);
}
if(arr[start+1]==0){
arr[start]=!arr[start];
arr[start+1]=!arr[start+1];
return true;
}else return false;
function solution(int arr[],int size)->int []{
for(int i=0;i<size;i++){
if(arr[i]==0){
if(!move(arr,i,size)) break;
}
}
return arr;
}
复杂度分析，最好情况n个0，O(n)遍历得到n-1个1+0，最坏情况0+n-2个1+0->n-2个1+01复杂度是O(n2)
投递华为等公司10个岗位 > 0 点赞 评论 收藏
分享
创作者周榜
更多
关注他的用户也关注了：