力扣3011. 判断一个数组是否可以变为有序（c++实现）

方法一：插入排序

        这是自个做的时候写的， 排序最一开始使用的冒泡排序，结果发现冒泡排序无法保证相邻这一条件，就改为了插入排序。

int cal_1(int a){     //判断该数有几个1
    int ans=0;
    while(a){
        a=a&(a-1);     //a=a&(a-1)能够实现每次运算使最右侧的1变为0，这样1的个数便很好判断了
        ans++;
    }
    return ans;
}
 
class Solution {
public:
    bool canSortArray(vector<int>& nums) {
 
        int len=nums.size();        
 //利用插入排序的思想进行排序，只不过判断条件多了个1的个数是否相等的判断
        for(int i=1,j;i<len;i++){   
            if(nums[i]<nums[i-1]&&cal_1(nums[i])==cal_1(nums[i-1])){
                int temp = nums[i];
                
                for(j=i-1;j>=0&&nums[j]>temp&&cal_1(nums[j])==cal_1(temp);j--){
                    nums[j+1]=nums[j];
                }
 
                nums[j+1]=temp;
            }
        }
 
        for(int i=1;i<len;i++){    //判断数组是否有序
            if(nums[i]<nums[i-1]) return false;
        }
        return true;
    }
};

以下方法是看了灵神的解析写的（灵神解析）

方法二：分组循环

适用场景：按照题目要求，数组会被分割成若干组，每一组的判断/处理逻辑是相同的。

该题我们可以分析出，数组可以通过每个数二进制中1的个数进行分割。

int cal_1(int a){
    int ans=0;
    while(a){
        a=a&(a-1);
        ans++;
    }
    return ans;
}
 
class Solution {
public:
    bool canSortArray(vector<int>& nums) {
 
        int len=nums.size();
 
        for(int i=0;i<len;){    //外层循环，每次循环就是分的一段
 
            int start = i;    //这一段的起始
            int n=cal_1(nums[i++]);    //这一段起始的1的个数
 
            while(i<len && cal_1(nums[i])==n){    //内层循环，寻找这一段的结尾
                i++;
            }
 
            sort(nums.begin()+start,nums.begin()+i);    //对这一段进行排序
 
        }
 
        return ranges::is_sorted(nums);    //判断最后的数组是否有序
 
    }
};

方法三：分组循环优化

其实每组没必要排序，经过分析可知，若这一组的值有小于上一组最大值的则不可能有序。 

int cal_1(int a){
    int ans=0;
    while(a){
        a=a&(a-1);
        ans++;
    }
    return ans;
}
 
class Solution {
public:
    bool canSortArray(vector<int>& nums) {
        int len = nums.size();
        int pre_max=0;    //上一组的最大值
        for(int i=0;i<len;){
            int n = cal_1(nums[i]);    //注意这里没有i++了，否则mx可能漏掉判断第一个数
            int mx=0;    //这一组的最大值
            while(i<len && cal_1(nums[i])==n){
                if(nums[i]<pre_max) return false;  //若这一组的数有小于上一组最大值的则false
                mx=max(mx,nums[i++]);    //更新这一组的最大值
            }
            pre_max=mx;    将这一组的最大值赋给pre_max，供下一组使用
        }
        return true;
    }
};