2024-05-25：用go语言，给定一个只包含正整数且下标从0开始的数组nums。 你可以执行以下操作： 如果两个相邻元素的二

2024-05-25：用go语言，给定一个只包含正整数且下标从0开始的数组nums。

你可以执行以下操作：

如果两个相邻元素的二进制表示中包含相同数量的1，

那么可以交换这两个元素。

你可以重复进行这个操作任意次数（包括0次）。

你的任务是判断能否通过这些操作使得数组变得有序。

如果可以，返回true；否则返回false。

输入：nums = [8,4,2,30,15]。

输出：true。

答案2024-05-25：

chatgpt

题目来自leetcode3011。

大体步骤如下：

1.定义了一个countOnes函数，用来计算一个整数的二进制表示中1的数量。

2.定义了canSortArray函数，用于判断能否通过题目描述的操作使得数组有序。

3.初始化preMax为0，用于记录前一个处理过的最大值。

4.开始遍历数组nums，用i来记录当前位置，n表示nums的长度。

5.对于每个位置i，将当前元素nums[i]视为mx（当前最大值）。

6.统计mx中1的数量，存储在变量ones中。

7.循环遍历直到相邻元素的二进制表示中包含相同数量的1为止，i会逐渐增加。

8.在循环中检查是否当前元素nums[i]小于preMax，若是，返回false。

9.否则，更新mx为较大的值。

10.更新preMax为mx。

11.返回true，表示可以通过操作使数组变得有序。

总的时间复杂度：

• countOnes函数的时间复杂度为O(log(maxNum))，其中maxNum表示数组中的最大值。

• 在canSortArray函数中，遍历数组一次，不超过n次。

• 因此，总的时间复杂度为O(nlog(maxNum))。

总的额外空间复杂度：

• 除了函数调用所需的栈空间外，没有使用额外的空间进行存储。

• 所以，总的额外空间复杂度为O(1)。

Go完整代码如下：

package main

import (

"fmt"

)

func countOnes(num int) int {

count := 0

for num > 0 {

count += num & 1

num >>= 1

}

return count

}

func canSortArray(nums []int) bool {

preMax := 0

for i, n := 0, len(nums); i < n; {

mx := nums[i]

ones := countOnes(mx)

for ; i < n && countOnes(nums[i]) == ones; i++ {

if nums[i] < preMax {

return false

}

if nums[i] > mx {

mx = nums[i]

}

}

preMax = mx

}

return true

}

func main() {

nums := []int{8, 4, 2, 30, 15}

fmt.Println(canSortArray(nums))

}

在这里插入图片描述Python完整代码如下：

# -*-coding:utf-8-*-

def count_ones(num):

count = 0

while num > 0:

count += num & 1

num >>= 1

return count

def can_sort_array(nums):

pre_max = 0

i = 0

n = len(nums)

while i < n:

mx = nums[i]

ones = count_ones(mx)

while i < n and count_ones(nums[i]) == ones:

if nums[i] < pre_max:

return False

if nums[i] > mx:

mx = nums[i]

i += 1

pre_max = mx

return True

nums = [8, 4, 2, 30, 15]

print(can_sort_array(nums))

在这里插入图片描述