Leetcode—3011. 判断一个数组是否可以变为有序【中等】（__builtin_popcount()、ranges::is_sorted())

2024每日刷题（144）

Leetcode—3011. 判断一个数组是否可以变为有序

O(n)复杂度实现代码

class Solution {
public:bool canSortArray(vector<int>& nums) {// 二进制数位下1数目相同的元素就不进行组内排序// 只进行分组// 当前组的值若小于上一组的最大值, 就立即返回falseint curMax = nums[0];int preMax = INT_MIN;for(int i = 0; i < nums.size(); i++) {int n = __builtin_popcount(nums[i]);while(i < nums.size() && __builtin_popcount(nums[i]) == n) {if(nums[i] < preMax) {return false;}curMax = max(curMax, nums[i]);i++;}preMax = curMax;i--;}return true;}
};

运行结果

sort实现代码

class Solution {
public:bool canSortArray(vector<int>& nums) {int start = 0;for(int i = 1; i < nums.size(); i++) {int n = __builtin_popcount(nums[start]);// 先找到二进制数位为1的数目相同组while(i < nums.size() && __builtin_popcount(nums[i]) == n) {i++;}// 然后组内冒泡排序ranges::sort(nums.begin() + start, nums.begin() + i);start = i;}return ranges::is_sorted(nums);}
};

运行结果

之后我会持续更新，如果喜欢我的文章，请记得一键三连哦，点赞关注收藏，你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 ！！！↖(▔▽▔)↗感谢支持！