JavaScript回文数算法优化：如何降低时间复杂度？

原代码通过将数字转为字符串后反转对比的方式实现，虽然逻辑简单，但需要额外的字符串存储空间，且反转整个字符串存在不必要的计算开销。我们可以通过直接操作数字反转后半部分的方式优化，既降低空间复杂度，也减少实际运算量。

优化思路 #

1. 提前排除特殊情况：
   • 负数不可能是回文数（负号无法对称），直接返回false；
   • 末尾为0但数字本身不是0的数（如10、200）不可能是回文数（回文数末尾不能为0，除非数字是0），直接返回false。
2. 反转数字的后半部分：
   • 循环提取数字的最后一位，逐步构建反转后的后半部分数字；
   • 当反转后的数字大于等于原数字剩余的前半部分时，停止循环（此时已处理完一半位数）。
3. 对比判断：
   • 若数字位数为偶数：反转后的后半部分数字应等于剩余的前半部分数字；
   • 若数字位数为奇数：反转后的后半部分数字除以10（去掉中间的单个数字）应等于剩余的前半部分数字。

优化后的代码 #

var isPalindrome = function(x) {
    // 处理特殊情况
    if (x < 0 || (x % 10 === 0 && x !== 0)) {
        return false;
    }

    let reversedHalf = 0;
    while (x > reversedHalf) {
        // 提取最后一位并添加到反转数中
        reversedHalf = reversedHalf * 10 + x % 10;
        // 去掉原数的最后一位
        x = Math.floor(x / 10);
    }

    // 偶数位直接对比，奇数位去掉反转数的最后一位（中间位）再对比
    return x === reversedHalf || x === Math.floor(reversedHalf / 10);
};

复杂度分析 #

• 时间复杂度：O(log₁₀x)，因为每次循环将数字除以10，循环次数等于数字位数的一半，而数字的位数是log₁₀x + 1，因此时间复杂度为对数级别。
• 空间复杂度：O(1)，仅使用了常数级别的额外空间，无需存储字符串。

内容的提问来源于stack exchange，提问作者Aaftab shekh