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
}