2231. 按奇偶性交换后的最大数字

🟢   🔖  排序 堆（优先队列）  🔗 力扣 LeetCode

题目

You are given a positive integer num. You may swap any two digits of num that have the same parity (i.e. both odd digits or both even digits).

Return the largest possible value of num afterany number of swaps.

Example 1:

Input: num = 1234

Output: 3412

Explanation: Swap the digit 3 with the digit 1, this results in the number 3214.

Swap the digit 2 with the digit 4, this results in the number 3412.

Note that there may be other sequences of swaps but it can be shown that 3412 is the largest possible number.

Also note that we may not swap the digit 4 with the digit 1 since they are of different parities.

Example 2:

Input: num = 65875

Output: 87655

Explanation: Swap the digit 8 with the digit 6, this results in the number 85675.

Swap the first digit 5 with the digit 7, this results in the number 87655.

Note that there may be other sequences of swaps but it can be shown that 87655 is the largest possible number.

Constraints:

• 1 <= num <= 10^9

题目大意

给你一个正整数 num 。你可以交换 num 中 奇偶性 相同的任意两位数字（即，都是奇数或者偶数）。

返回交换 任意 次之后 num 的 最大 可能值。

示例 1：

输入： num = 1234

输出： 3412

解释： 交换数字 3 和数字 1 ，结果得到 3214 。

交换数字 2 和数字 4 ，结果得到 3412 。

注意，可能存在其他交换序列，但是可以证明 3412 是最大可能值。

注意，不能交换数字 4 和数字 1 ，因为它们奇偶性不同。

示例 2：

输入： num = 65875

输出： 87655

解释： 交换数字 8 和数字 6 ，结果得到 85675 。

交换数字 5 和数字 7 ，结果得到 87655 。

注意，可能存在其他交换序列，但是可以证明 87655 是最大可能值。

提示：

• 1 <= num <= 10^9

解题思路

1. 分离奇偶数字：

   • 遍历 num 的每一位，按照奇偶性将数字分别存储在 odd 和 even 数组中，同时记录其奇偶性到 parity 数组中，保留其在原始数字中的顺序。

2. 对奇偶数字分别排序：

   • 将 odd 和 even 分别从小到大排序，以便后续能从数组中提取最大值。

3. 根据奇偶性重组数字：

   • 从 parity 数组中逆序遍历，根据奇偶性从对应的 odd 或 even 数组中取出最大值，并将其放回到结果数字中。

4. 返回结果：

   • 重建后的数字即为答案。

复杂度分析

• 时间复杂度：O(d log d)，其中 d 是数字的位数，排序奇偶数字的时间开销。
• 空间复杂度：O(d)，使用了 odd、even 和 parity 数组存储数字及其奇偶性。

代码

/**
 * @param {number} num
 * @return {number}
 */
var largestInteger = function (num) {
	let parity = [];
	let odd = [];
	let even = [];

	// 分离奇偶数字，同时记录奇偶性
	while (num > 0) {
		const digit = num % 10;
		num = Math.floor(num / 10);
		if (digit % 2 === 0) {
			even.push(digit);
			parity.push(0); // 偶数标记
		} else {
			odd.push(digit);
			parity.push(1); // 奇数标记
		}
	}

	// 对奇偶数字分别排序
	even.sort((a, b) => a - b);
	odd.sort((a, b) => a - b);

	let res = 0;
	// 根据奇偶性重组数字
	for (let i = parity.length - 1; i >= 0; i--) {
		if (parity[i] === 1) {
			res = res * 10 + odd.pop(); // 奇数
		} else {
			res = res * 10 + even.pop(); // 偶数
		}
	}

	return res;
};

相关题目

题号	标题	题解	标签	难度	力扣
747	至少是其他数字两倍的最大数	[✓]	数组 排序	🟢	🀄️ 🔗
905	按奇偶排序数组	[✓]	数组 双指针 排序	🟢	🀄️ 🔗
922	按奇偶排序数组 II	[✓]	数组 双指针 排序	🟢	🀄️ 🔗
1202	交换字符串中的元素		深度优先搜索 广度优先搜索 并查集 4+	🟠	🀄️ 🔗
2149	按符号重排数组		数组 双指针 模拟	🟠	🀄️ 🔗