题目描述

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

现以某种顺序 连接 数组 nums 中所有元素的 二进制表示，请你返回可以由这种方法形成的 最大 数值。

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

样例

输入: nums = [1,2,3]

输出: 30

解释:

按照顺序 [3, 1, 2] 连接数字的二进制表示，得到结果 "11110"，这是 30 的二进制表示。

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

输出: 1296

解释:

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

限制

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

算法

(排序) $O(n \log n \log U)$

1. 将所有数字转为二进制字符串。
2. 排序下标数组，如果数字 $x$ 需要排在 $y$ 之前，当且仅当 $x$ 的二进制字符串拼上 $y$ 的二进制字符串大于 $y$ 的二进制字符串拼上 $x$ 的二进制字符串。
3. 排序后，按照顺序拼接并还原最终的值。

时间复杂度

• 转二进制字符串的时间复杂度为 $O(n \log U)$。
• 排序的时间复杂度为 $O(n \log n \log U)$。
• 还原答案的时间复杂度为 $O(n \log U)$。
• 故总时间复杂度为 $O(n \log n \log U)$。

空间复杂度

• 需要 $O(n \log U)$ 的额外空间存储所有的二进制字符串，排序的下标数组和系统栈。

C++ 代码

class Solution {
public:
    int maxGoodNumber(vector<int>& nums) {
        const int n = nums.size();
        vector<string> bnums(n);
        vector<int> idx(n);

        for (int i = 0; i < n; i++) {
            idx[i] = i;

            for (int x = nums[i]; x; x >>= 1)
                bnums[i] += (x & 1) + '0';

            reverse(bnums[i].begin(), bnums[i].end());
        }

        sort(idx.begin(), idx.end(), [&](int x, int y) {
            return bnums[x] + bnums[y] > bnums[y] + bnums[x];
        });

        string res;
        for (int i = 0; i < n; i++)
            res += bnums[idx[i]];

        int ans = 0;
        for (char c : res)
            ans = ans * 2 + c - '0';

        return ans;
    }
};