2025-05-05：连接二进制表示可形成的最大数值。用go语言，给定一个包含三个整数的数组 nums。 将数组中所有元素的二进

2025-05-05：连接二进制表示可形成的最大数值。用go语言，给定一个包含三个整数的数组 nums。

将数组中所有元素的二进制形式以某种顺序拼接起来，要求拼接后的二进制字符串所表示的数值尽可能大。

其中，每个数字的二进制表示不包含前导零。

请你返回通过这种方式能得到的最大数值。

nums.length == 3。

1 <= nums[i] <= 127。

输入: nums = [2,8,16]。

输出: 1296。

解释:

按照顺序 [2, 8, 16] 连接数字的二进制表述，得到结果 "10100010000"，这是 1296 的二进制表示。

题目来自leetcode3309。

分步骤描述过程：

1. 1. 理解题目要求：
   • • 给定三个整数，需要将它们按某种顺序排列，然后将它们的二进制表示按顺序拼接起来，形成一个更大的二进制数。
   • • 这个拼接后的二进制数不能有前导零（即每个数字的二进制表示本身没有前导零，拼接时也不会引入前导零）。
   • • 目标是找到一种排列顺序，使得拼接后的二进制数对应的十进制值最大。
2. 2. 示例分析：
   • • 输入 nums = [2, 8, 16]：
     • • 2 的二进制是 10（长度 2）
     • • 8 的二进制是 1000（长度 4）
     • • 16 的二进制是 10000（长度 5）
   • • 可能的拼接顺序：
     • • [2, 8, 16] -> "10" + "1000" + "10000" -> 10100010000（1296）
     • • [2, 16, 8] -> "10" + "10000" + "1000" -> 10100001000（1288）
     • • [8, 2, 16] -> "1000" + "10" + "10000" -> 10001010000（1104）
     • • [8, 16, 2] -> "1000" + "10000" + "10" -> 10001000010（1090）
     • • [16, 2, 8] -> "10000" + "10" + "1000" -> 10000101000（1064）
     • • [16, 8, 2] -> "10000" + "1000" + "10" -> 10000100010（1042）
   • • 最大值为 10100010000（1296），对应顺序 [2, 8, 16]。
3. 3. 排序策略：
   • • 为了找到最优的拼接顺序，需要对三个数字进行排序。
   • • 排序的比较规则是：对于两个数字 a 和 b，比较 (b << lenA | a) 和 (a << lenB | b)，其中 lenA 和 lenB 分别是 a 和 b 的二进制位数。
   • • 如果 (b << lenA | a) > (a << lenB | b)，则 a 应该排在 b 前面，否则 b 排在前面。
   • • 这种比较规则确保拼接后的二进制数尽可能大。
4. 4. 排序过程：
   • • 对于 nums = [2, 8, 16]：
     • • 比较 2 和 8：
       • • lenA = 2, lenB = 4
       • • (8 << 2 | 2) = 32 | 2 = 34
       • • (2 << 4 | 8) = 32 | 8 = 40
       • • 34 < 40，所以 8 应该排在 2 前面。
     • • 比较 8 和 16：
       • • lenA = 4, lenB = 5
       • • (16 << 4 | 8) = 256 | 8 = 264
       • • (8 << 5 | 16) = 256 | 16 = 272
       • • 264 < 272，所以 16 应该排在 8 前面。
     • • 比较 2 和 16：
       • • lenA = 2, lenB = 5
       • • (16 << 2 | 2) = 64 | 2 = 66
       • • (2 << 5 | 16) = 64 | 16 = 80
       • • 66 < 80，所以 16 应该排在 2 前面。
     • • 最终排序顺序：[2, 8, 16]。
5. 5. 拼接二进制：
   • • 按排序后的顺序 [2, 8, 16] 拼接二进制：
     • • 2 -> 10
     • • 8 -> 1000
     • • 16 -> 10000
     • • 拼接结果：10100010000。
   • • 转换为十进制：10100010000 -> 1*2^10 + 0*2^9 + 1*2^8 + 0*2^7 + 0*2^6 + 0*2^5 + 1*2^4 + 0*2^3 + 0*2^2 + 0*2^1 + 0*2^0 = 1024 + 256 + 16 = 1296。
6. 6. 计算最终结果：
   • • 将排序后的数字依次拼接二进制表示，然后转换为十进制，得到最大值 1296。

时间复杂度和额外空间复杂度：

• • 时间复杂度：
  • • 排序的时间复杂度：由于只有 3 个数字，排序的比较次数是常数（最多 3 次比较），每次比较的计算也是常数时间（计算位数和移位操作）。
  • • 计算二进制位数的时间：bits.Len 是 O(1) 操作。
  • • 拼接二进制的时间：遍历排序后的数组，拼接操作是常数时间（因为数字的二进制位数最多是 7 位，即 127 的二进制是 1111111）。
  • • 总体时间复杂度是 O(1)（因为输入规模固定为 3）。
• • 额外空间复杂度：
  • • 排序可能需要 O(1) 的额外空间（原地排序）。
  • • 没有使用额外的数据结构，空间复杂度是 O(1)。

Go完整代码如下：

package main

import (
    "fmt"
    "slices"
    "math/bits"
)

func maxGoodNumber(nums []int) (ans int) {
    slices.SortFunc(nums, func(a, b int)int {
        lenA := bits.Len(uint(a))
        lenB := bits.Len(uint(b))
        return (b<<lenA | a) - (a<<lenB | b)
    })

    for _, x := range nums {
        ans = ans<<bits.Len(uint(x)) | x
    }
    return
}


func main() {
    nums := []int{2,8,16}
    result := maxGoodNumber(nums)
    fmt.Println(result)
}

Python完整代码如下：

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

from functools import cmp_to_key

defmax_good_number(nums):
    defcompare(a, b):
        lenA = a.bit_length()
        lenB = b.bit_length()
        # 模拟 Go 中位运算构造的比较方式
        val1 = (b << lenA) | a
        val2 = (a << lenB) | b
        # 返回正负决定排序顺序
        return val2 - val1  # 因为 Go排序传入返回 a-b，Python中 cmp 返回 <0表示a<b，所以反向用了 val2 - val1

    nums.sort(key=cmp_to_key(compare))
    ans = 0
    for x in nums:
        ans = (ans << x.bit_length()) | x
    return ans


if __name__ == "__main__":
    nums = [2, 8, 16]
    result = max_good_number(nums)
    print(result)