Easy

题目描述

给你一个正整数 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. 由于只能交换相同奇偶性的数字，我们可以将奇数位和偶数位分别处理
  2. 为了使数字最大，应该让较大的数字尽可能出现在高位
  3. 因此，我们可以将所有奇数数字和偶数数字分别按降序排列
  4. 然后按原位置的奇偶性，依次分配最大的可用数字

算法步骤：

  1. 将数字转换为字符串，便于操作每一位
  2. 遍历字符串，将奇数位和偶数位分别收集到两个数组中
  3. 对两个数组分别按降序排序
  4. 再次遍历原字符串，根据当前位置的奇偶性，从对应的排序数组中取出最大的可用数字
  5. 将结果转换回整数

这种方法的时间复杂度主要来自于排序操作，由于数字最多9位，所以实际复杂度很低。

推荐解法： 分离奇偶数字并排序的贪心策略。

代码实现

class Solution {
public:
    int largestInteger(int num) {
        string s = to_string(num);
        vector<char> odds, evens;
        
        // 收集奇数和偶数数字
        for (char c : s) {
            if ((c - '0') % 2 == 0) {
                evens.push_back(c);
            } else {
                odds.push_back(c);
            }
        }
        
        // 按降序排序
        sort(odds.rbegin(), odds.rend());
        sort(evens.rbegin(), evens.rend());
        
        // 重构数字
        int oddIndex = 0, evenIndex = 0;
        for (int i = 0; i < s.length(); i++) {
            if ((s[i] - '0') % 2 == 0) {
                s[i] = evens[evenIndex++];
            } else {
                s[i] = odds[oddIndex++];
            }
        }
        
        return stoi(s);
    }
};

class Solution:
    def largestInteger(self, num: int) -> int:
        s = str(num)
        odds = []
        evens = []
        
        # 收集奇数和偶数数字
        for c in s:
            if int(c) % 2 == 0:
                evens.append(c)
            else:
                odds.append(c)
        
        # 按降序排序
        odds.sort(reverse=True)
        evens.sort(reverse=True)
        
        # 重构数字
        result = []
        odd_index = 0
        even_index = 0
        
        for c in s:
            if int(c) % 2 == 0:
                result.append(evens[even_index])
                even_index += 1
            else:
                result.append(odds[odd_index])
                odd_index += 1
        
        return int(''.join(result))

public class Solution {
    public int LargestInteger(int num) {
        string s = num.ToString();
        List<char> odds = new List<char>();
        List<char> evens = new List<char>();
        
        // 收集奇数和偶数数字
        foreach (char c in s) {
            if ((c - '0') % 2 == 0) {
                evens.Add(c);
            } else {
                odds.Add(c);
            }
        }
        
        // 按降序排序
        odds.Sort((a, b) => b.CompareTo(a));
        evens.Sort((a, b) => b.CompareTo(a));
        
        // 重构数字
        char[] result = new char[s.Length];
        int oddIndex = 0, evenIndex = 0;
        
        for (int i = 0; i < s.Length; i++) {
            if ((s[i] - '0') % 2 == 0) {
                result[i] = evens[evenIndex++];
            } else {
                result[i] = odds[oddIndex++];
            }
        }
        
        return int.Parse(new string(result));
    }
}

var largestInteger = function(num) {
    let digits = num.toString().split('').map(Number);
    let odds = [];
    let evens = [];
    
    for (let digit of digits) {
        if (digit % 2 === 0) {
            evens.push(digit);
        } else {
            odds.push(digit);
        }
    }
    
    odds.sort((a, b) => b - a);
    evens.sort((a, b) => b - a);
    
    let oddIndex = 0;
    let evenIndex = 0;
    let result = [];
    
    for (let digit of digits) {
        if (digit % 2 === 0) {
            result.push(evens[evenIndex++]);
        } else {
            result.push(odds[oddIndex++]);
        }
    }
    
    return parseInt(result.join(''));
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(d log d)d 是数字的位数，最多9位，主要时间消耗在排序上
空间复杂度O(d)需要额外空间存储奇数和偶数数字，以及结果字符串

相关题目