寻找最近的回文数

题目描述（来源于LeetCode)

给定一个表示整数的字符串 n ，返回与它最近的回文整数（不包括自身）。如果不止一个，返回较小的那个。

“最近的”定义为两个整数差的绝对值最小。

代码实现

初期思路

class Solution:
    def nearestPalindromic(self, n: str) -> str:
        a= int(n)
        b= int(n)
        max =a
        while 1:
            a+=1
            if str(a)==str(a)[::-1]:
                max=a
                break
        while 1:
            b-=1
            if str(b)==str(b)[::-1]:
                min=b
                break
        if max+min-2*int(n)>=0:
            return str(min)
        else:
            return str(max)

虽然可以实现但如果输入的n很特殊则效率很低

情况改善

class Solution:
    def nearestPalindromic(self, n: str) -> str:
        num = int(n)
        len_n = len(n)
        
        if num <= 10:
            return str(num - 1)
        
        candidates = set()
        candidates.add(10**(len_n - 1) - 1)
        candidates.add(10**(len_n) + 1)
        
        half_len = (len_n + 1) // 2
        prefix = n[:half_len]
        prefix_int = int(prefix)
        
        for p in [prefix_int - 1, prefix_int, prefix_int + 1]:
            s_p = str(p)
            if len(s_p) != half_len:
                continue
            if len_n % 2 == 0:
                candidate_str = s_p + s_p[::-1]
            else:
                candidate_str = s_p + s_p[::-1][1:]
            candidates.add(int(candidate_str))
        
        if num in candidates:
            candidates.remove(num)
        min_diff = float('inf')
        result = None
        for cand in candidates:
            diff = abs(cand - num)
            if diff < min_diff:
                min_diff = diff
                result = cand
            elif diff == min_diff:
                if cand < result:
                    result = cand
        return str(result)

参考昨天做的题19中的思路，先找出范围内的回文数，在进行匹配

复杂度分析

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$