C++中如何高效判断一个数是否为回文数字？

Question

在C++中判断一个整数是否为回文时，常见问题是：如何在不使用额外空间（如字符串或数组）的情况下高效反转数字的一半并进行比较？尤其当输入可能溢出时，直接反转整个整数可能导致int溢出，影响正确性。此外，负数显然不是回文数，需优先处理符号问题。一个高效解法是仅反转数字的后半部分，并与前半部分比较，从而实现时间复杂度O(log n)、空间复杂度O(1)。但如何准确判断“一半”的边界？例如，当原始数字位数为奇数时，如何忽略中间位？这些问题直接影响算法的鲁棒性与效率。

Answer 1

在C++中高效判断整数回文：从基础到鲁棒性优化

1. 问题背景与核心挑战

判断一个整数是否为回文（palindrome）是算法面试和实际开发中的经典问题。直观思路是将整数转换为字符串，然后比较其与反转后的字符串是否相等。然而，该方法需要额外的存储空间（O(log n)），违背了“不使用额外空间”的约束条件。

更进一步地，在C++中直接反转整个整数可能导致 int 溢出。例如，当输入为 1999999999 时，其反转值远超 INT_MAX，导致未定义行为。因此，必须设计一种避免溢出且空间复杂度为 O(1) 的解法。

• 负数不是回文数，需优先处理符号
• 个位数（0-9）均为回文数
• 以0结尾但非0本身的数不是回文（如10、100）
• 仅需比较数字前半部分与后半部分的反转即可

2. 核心思想：反转一半数字

关键洞察在于：我们不需要完全反转整个数字，只需将后半部分反转，并与前半部分进行比较。这样可以：

1. 避免整数溢出风险
2. 实现 O(log n) 时间复杂度（n为数值大小）
3. 保持 O(1) 空间复杂度

例如：

原数	前半部分	后半反转	是否回文
1221	12	12	是
12321	12	12	是（忽略中间3）
123	1	32	否

3. 边界判断：“一半”如何定义？

确定何时停止反转是算法正确性的关键。我们通过不断从原始数中提取末位并构建反转数，直到反转数大于等于原数的一半为止。

具体终止条件为：

while (reversed < original) {
    reversed = reversed * 10 + original % 10;
    original /= 10;
}

此时有两种情况：

• 数字位数为偶数：original == reversed → 回文
• 数字位数为奇数：original == reversed / 10 → 忽略中间位

4. 完整C++实现代码

#include <iostream>
#include <climits>

bool isPalindrome(int x) {
    // 负数或以0结尾但非0本身，均不是回文
    if (x < 0 || (x % 10 == 0 && x != 0)) {
        return false;
    }

    int reversed = 0;
    while (reversed < x) {
        reversed = reversed * 10 + x % 10;
        x /= 10;
    }

    // 偶数长度：x == reversed
    // 奇数长度：x == reversed / 10（忽略中间位）
    return x == reversed || x == reversed / 10;
}

// 测试用例
int main() {
    std::cout << isPalindrome(121) << std::endl;     // true
    std::cout << isPalindrome(-121) << std::endl;    // false
    std::cout << isPalindrome(1221) << std::endl;    // true
    std::cout << isPalindrome(10) << std::endl;      // false
    return 0;
}

5. 算法流程图解析

graph TD A[开始] --> B{x < 0 或 (x % 10 == 0 且 x != 0)} B -- 是 --> C[返回 false] B -- 否 --> D[reversed = 0] D --> E{reversed < x} E -- 是 --> F[reversed = reversed * 10 + x % 10] F --> G[x = x / 10] G --> E E -- 否 --> H{x == reversed 或 x == reversed / 10} H -- 是 --> I[返回 true] H -- 否 --> J[返回 false]

6. 鲁棒性分析与边界场景

考虑以下典型边缘情况：

输入	预期输出	说明
0	true	单个数字是回文
-1	false	负数非回文
10	false	结尾为0但非0本身
12321	true	奇数长度，忽略中间位
123321	true	偶数长度，完全对称
INT_MAX	false	大数测试，无溢出
1000000001	true	长回文，验证逻辑
12345	false	普通非回文
11	true	最小偶数回文
7	true	单数字

7. 性能与扩展思考

本算法时间复杂度为 O(log n)，因为每次循环都将原数除以10，相当于处理其十进制位数。空间上仅使用两个整型变量，满足 O(1) 要求。

进一步可扩展至其他进制回文判断（如二进制、十六进制），只需将 %10 和 /10 替换为对应进制基数即可。

对于更大范围的整数（如 long long），算法结构不变，仍能有效防止溢出。