3011. Find if Array Can Be Sorted
有一个0-indexed的正整数矩阵 : nums
在每个操作你可以把满足以下条件相邻的两个元素位置交换
这两个元素用2进位表示时，1(set bits)的数量是相等的
可以进行任意次操作
请问有办法把nums变成有序(递增)的矩阵吗
思路:
就记录每个元素的1的数量
接着把nums分成多个相同set bits数量的区块
接着把每个区块都排序后
检查是不是整个矩阵是递增排列
golang code :
func canSortArray(nums []int) bool {
n := len(nums)
NumOfSetbit := make([]int, n)
MinNumArray := []int{}
for i := 0; i < n; i++ {
NumOfSetbit[i] = CntSetbit(nums[i])
}
left := 0
for i := 1; i < n; i++ {
if NumOfSetbit[i] != NumOfSetbit[i-1] {
slices.Sort(nums[left:i])
MinNumArray = append(MinNumArray, nums[left])
MinNumArray = append(MinNumArray, nums[i-1])
left = i
}
}
slices.Sort(nums[left:n])
MinNumArray = append(MinNumArray, nums[left])
MinNumArray = append(MinNumArray, nums[n-1])
for i := 1; i < len(MinNumArray); i++ {
if MinNumArray[i-1] > MinNumArray[i] {
return false
}
}
return true
}
func CntSetbit(num int) int {
ans := 0
for num > 0 {
if num&1 > 0 {
ans++
}
num >>= 1
}
return ans
}