3011.数组是否可以变为有序

给你一个下标从 0 开始且全是 正 整数的数组 nums 。

一次 操作 中，如果两个 相邻 元素在二进制下数位为 1 的数目 相同 ，那么你可以将这两个元素交换。你可以执行这个操作 任意次 （也可以 0 次）。

如果你可以使数组变有序，请你返回 true ，否则返回 false 。

相关函数

__builtin_popcount(int): GCC提供的内建函数，返回一个整数中"1"的二进制个数。

fmax(int, int)：C 标准库函数，返回两个浮点数中较大的一个。尽管它通常用于浮点数，但在某些编译器实现中，它也可以接受整数并返回较大的那个。（本题中使用 max() 函数也没有问题）

思路

一次操作中，相邻元素在二进制下数位为 1 的数目相同就可以交换这两个元素。我们可以将数组的元素进行分组，同时分组满足以下的条件：

• 每个分组中的元素，其二进制含有“1”的数量相同。

这样我们就能够维护多个能够实现分组内元素位置能够进行互相交换的分组了。所以一个分组内，无论其如何排序，我们总是能够将这个分组内的元素交换位置从而得到一个递增的分组。

我们现在已经完成了每个分组内的有序，如何保证分组间递增呢？很简单，我们维护上一个分组的最大值lastGroupMax，同时让当前的分组值与最大值进行比较，如果当前分组值小于上一个分组的最大值，意味着不满足递增的逻辑，就不满足数组可以变为有序数组。

待到结束整个数组的遍历后，我们就能够得到一个可以变为有序的数组，因此返回True。

代码

class Solution{
public:
    bool canSortArray(vector<int>& nums) {
        int lastCnt = 0;
        int curGroupMax = 0, lastGroupMax = 0;

        for (int i = 0; i < nums.size(); i++) {
            int num = nums[i];
            int curCnt = __builtin_popcount(num); // 统计当前元素“1”的个数
            /** 维护二进制元素“1”个数相同的元素 */
            if (curCnt == lastCnt) {
                curGroupMax = max(curGroupMax, num); // 维护组最大值
            } else { 
                lastCnt = curCnt;
                lastGroupMax = curGroupMax;
                curGroupMax = num;
            }
            if (num < lastGroupMax) {
                return false;
            }
        }
        
        return true;
    }
};

• lastCnt和curCnt用于遍历并统计当前元素二进制中“1”的个数

• lastGroupMax和curGroupMax用于维护当前分组的元素最大值