Medium

题目描述

给你一个仅由数字组成的字符串 num。

返回可以由 num 中的数字形成的最大回文整数（以字符串形式返回）。该整数不应包含前导零。

注意：

  • 你不需要使用 num 中的所有数字，但必须至少使用一个数字。
  • 数字可以重新排列。

示例 1：

输入：num = "444947137"
输出："7449447"
解释：
使用 "444947137" 中的数字 "4449477" 来形成回文整数 "7449447"。
可以证明 "7449447" 是可以形成的最大回文整数。

示例 2：

输入：num = "00009"
输出："9"
解释：
可以证明 "9" 是可以形成的最大回文整数。
注意返回的整数不应包含前导零。

约束条件：

  • 1 <= num.length <= 10^5
  • num 由数字组成

解题思路

这道题要求构造最大的回文数，可以分为以下几个步骤：

  1. 统计频次：统计每个数字的出现次数

  2. 构造策略：

    • 回文数的特点是左右对称，所以除了中间位置外，其他位置的数字必须成对出现
    • 为了构造最大回文数，应该优先使用较大的数字
    • 从数字9到1，如果某个数字出现次数≥2，就在左半部分放置该数字的一半

  3. 处理中间位置：如果存在出现奇数次的数字，选择其中最大的一个放在中间

  4. 特殊情况处理：

    • 如果构造的左半部分全是0，说明只能选择一个非零数字作为结果
    • 注意避免前导零的问题

  5. 构造结果：将左半部分 + 中间数字（如果有）+ 左半部分的逆序组合成最终回文数

时间复杂度主要在于遍历字符串统计频次，整体算法简洁高效。

代码实现

class Solution {
public:
    string largestPalindromic(string num) {
        vector<int> count(10, 0);
        for (char c : num) {
            count[c - '0']++;
        }
        
        string left = "";
        string middle = "";
        
        // 从9到0构造左半部分
        for (int i = 9; i >= 0; i--) {
            if (i == 0 && left.empty()) {
                // 避免前导零，但0可以作为中间数字
                continue;
            }
            
            // 成对使用数字构造左半部分
            int pairs = count[i] / 2;
            left += string(pairs, '0' + i);
            count[i] -= pairs * 2;
        }
        
        // 找到最大的剩余数字作为中间数字
        for (int i = 9; i >= 0; i--) {
            if (count[i] > 0) {
                middle = '0' + i;
                break;
            }
        }
        
        // 如果左半部分为空，只返回中间数字
        if (left.empty()) {
            return middle.empty() ? "0" : middle;
        }
        
        string right = left;
        reverse(right.begin(), right.end());
        return left + middle + right;
    }
};

class Solution:
    def largestPalindromic(self, num: str) -> str:
        count = [0] * 10
        for c in num:
            count[int(c)] += 1
        
        left = []
        middle = ""
        
        # 从9到0构造左半部分
        for i in range(9, -1, -1):
            if i == 0 and not left:
                # 避免前导零
                continue
            
            # 成对使用数字构造左半部分
            pairs = count[i] // 2
            left.extend([str(i)] * pairs)
            count[i] -= pairs * 2
        
        # 找到最大的剩余数字作为中间数字
        for i in range(9, -1, -1):
            if count[i] > 0:
                middle = str(i)
                break
        
        # 如果左半部分为空，只返回中间数字
        if not left:
            return middle if middle else "0"
        
        left_str = ''.join(left)
        right_str = left_str[::-1]
        return left_str + middle + right_str

public class Solution {
    public string LargestPalindromic(string num) {
        int[] count = new int[10];
        foreach (char c in num) {
            count[c - '0']++;
        }
        
        StringBuilder left = new StringBuilder();
        string middle = "";
        
        // 从9到0构造左半部分
        for (int i = 9; i >= 0; i--) {
            if (i == 0 && left.Length == 0) {
                // 避免前导零
                continue;
            }
            
            // 成对使用数字构造左半部分
            int pairs = count[i] / 2;
            left.Append(new string((char)('0' + i), pairs));
            count[i] -= pairs * 2;
        }
        
        // 找到最大的剩余数字作为中间数字
        for (int i = 9; i >= 0; i--) {
            if (count[i] > 0) {
                middle = ((char)('0' + i)).ToString();
                break;
            }
        }
        
        // 如果左半部分为空，只返回中间数字
        if (left.Length == 0) {
            return string.IsNullOrEmpty(middle) ? "0" : middle;
        }
        
        string leftStr = left.ToString();
        char[] rightArray = leftStr.ToCharArray();
        Array.Reverse(rightArray);
        string rightStr = new string(rightArray);
        
        return leftStr + middle + rightStr;
    }
}

var largestPalindromic = function(num) {
    const count = new Array(10).fill(0);
    
    for (let char of num) {
        count[parseInt(char)]++;
    }
    
    let left = '';
    let middle = '';
    
    for (let i = 9; i >= 0; i--) {
        if (i === 0 && left === '' && count[i] > 0) {
            if (count[i] % 2 === 1) {
                middle = '0';
            }
            continue;
        }
        
        if (count[i] >= 2) {
            const pairs = Math.floor(count[i] / 2);
            left += i.toString().repeat(pairs);
        }
        
        if (count[i] % 2 === 1 && middle === '') {
            middle = i.toString();
        }
    }
    
    if (left === '' && middle === '') {
        return '0';
    }
    
    const result = left + middle + left.split('').reverse().join('');
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)n为字符串长度，需要遍历一次统计频次，构造过程为常数时间
空间复杂度O(1)除了结果字符串外，只使用了固定大小的计数数组

相关题目