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

福大大架构师每日一题

发布于 2024-05-27 17:26:14

700

发布于 2024-05-27 17:26:14

文章被收录于专栏：福大大架构师每日一题

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))