Medium

题目描述

给你一个长度为 3 的整数数组 nums。

返回通过将 nums 中所有元素的二进制表示按某种顺序串联形成的最大可能数字。

注意，任何数字的二进制表示都不包含前导零。

示例 1：

输入: nums = [1,2,3]
输出: 30
解释:
按顺序 [3, 1, 2] 串联数字得到结果 "11110"，这是 30 的二进制表示。

示例 2：

输入: nums = [2,8,16]
输出: 1296
解释:
按顺序 [2, 8, 16] 串联数字得到结果 "10100010000"，这是 1296 的二进制表示。

约束条件：

  • nums.length == 3
  • 1 <= nums[i] <= 127

提示：

  • 有多少种可能的串联顺序？

解题思路

这道题的核心思路是找到三个数字的最优排列顺序，使得它们的二进制表示串联后形成的数字最大。

由于数组长度固定为3，我们可以暴力枚举所有可能的排列。对于三个元素，总共有3! = 6种排列方式。

关键思路是：

  1. 生成所有排列：枚举6种可能的排列顺序
  2. 二进制串联：对于每种排列，将数字转换为二进制字符串并串联
  3. 转换为十进制：将串联后的二进制字符串转换为十进制数
  4. 取最大值：比较所有可能的结果，返回最大值

另一种更高效的思路是使用自定义比较器：比较两个数字a和b，如果"a的二进制+b的二进制" > “b的二进制+a的二进制”，则a应该排在b前面。但由于题目限定数组长度为3，暴力枚举更直观简单。

实现时需要注意：

  • 获取数字的二进制表示（去除"0b"前缀）
  • 正确进行字符串串联
  • 将二进制字符串转换为十进制数

代码实现

class Solution {
public:
    int maxGoodNumber(vector<int>& nums) {
        vector<int> perm = {0, 1, 2};
        int maxNum = 0;
        
        do {
            string binary = "";
            for (int i : perm) {
                binary += bitset<32>(nums[i]).to_string().substr(bitset<32>(nums[i]).to_string().find('1'));
            }
            int currentNum = stoi(binary, 0, 2);
            maxNum = max(maxNum, currentNum);
        } while (next_permutation(perm.begin(), perm.end()));
        
        return maxNum;
    }
};

class Solution:
    def maxGoodNumber(self, nums: List[int]) -> int:
        from itertools import permutations
        
        max_num = 0
        
        for perm in permutations(nums):
            binary_str = ""
            for num in perm:
                binary_str += bin(num)[2:]  # Remove '0b' prefix
            
            current_num = int(binary_str, 2)
            max_num = max(max_num, current_num)
        
        return max_num

public class Solution {
    public int MaxGoodNumber(int[] nums) {
        int maxNum = 0;
        
        // Generate all 6 permutations manually for array of size 3
        int[][] permutations = {
            new int[] {nums[0], nums[1], nums[2]},
            new int[] {nums[0], nums[2], nums[1]},
            new int[] {nums[1], nums[0], nums[2]},
            new int[] {nums[1], nums[2], nums[0]},
            new int[] {nums[2], nums[0], nums[1]},
            new int[] {nums[2], nums[1], nums[0]}
        };
        
        foreach (var perm in permutations) {
            string binaryStr = "";
            foreach (int num in perm) {
                binaryStr += Convert.ToString(num, 2);
            }
            
            int currentNum = Convert.ToInt32(binaryStr, 2);
            maxNum = Math.Max(maxNum, currentNum);
        }
        
        return maxNum;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxGoodNumber = function(nums) {
    const getBinary = (num) => num.toString(2);
    
    const permutations = [
        [0, 1, 2],
        [0, 2, 1],
        [1, 0, 2],
        [1, 2, 0],
        [2, 0, 1],
        [2, 1, 0]
    ];
    
    let maxValue = 0;
    
    for (const perm of permutations) {
        const binaryStr = perm.map(i => getBinary(nums[i])).join('');
        const value = parseInt(binaryStr, 2);
        maxValue = Math.max(maxValue, value);
    }
    
    return maxValue;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(1) - 由于数组长度固定为3，排列数固定为6，每次操作的时间复杂度都是常数
空间复杂度O(1) - 使用常数额外空间存储排列和二进制字符串

相关题目