3309. 连接二进制表示可形成的最大数值

🟠   🔖  位运算 数组 枚举  🔗 力扣 LeetCode

题目

You are given an array of integers nums of size 3.

Return the maximum possible number whose binary representation can be formed by concatenating the binary representation of all elements in nums in some order.

Note that the binary representation of any number does not contain leading zeros.

Example 1:

Input: nums = [1,2,3]

Output: 30

Explanation:

Concatenate the numbers in the order [3, 1, 2] to get the result "11110", which is the binary representation of 30.

Example 2:

Input: nums = [2,8,16]

Output: 1296

Explanation:

Concatenate the numbers in the order [2, 8, 16] to get the result "10100010000", which is the binary representation of 1296.

Constraints:

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

题目大意

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

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

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

解题思路

本题的关键在于如何比较两个数 a 和 b 的拼接顺序。我们需要比较 a+b 和 b+a，判断哪种拼接方式会生成更大的数。通过这样的比较来决定排序的优先级。

1. 将每个整数转换为二进制字符串。
2. 使用自定义的排序函数来比较两两拼接的结果，按从大到小的顺序排序。
3. 排序完成后，将这些二进制字符串拼接在一起。

复杂度分析

• 时间复杂度：O(m * n log n)，其中 n 是数组的长度，m 是二进制字符串的平均长度，排序的时间复杂度为 O(n log n)，由于每次比较涉及字符串操作，故总体时间复杂度为 O(m * n log n)
• 空间复杂度：O(n)，额外空间主要用于存储二进制字符串。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxGoodNumber = function (nums) {
	let binaryArr = nums.map((num) => num.toString(2));
	binaryArr.sort((a, b) => b + a - (a + b));
	return parseInt(binaryArr.join(''), 2);
};

相关题目

题号	标题	题解	标签	难度
1680	连接连续二进制数字		位运算 数学 模拟