高效演算法：求比指定數大且最小的「不重複數」 (相鄰位數不相同)

給定正整數 N，找出大於 N 的最小整數，使其十進制表示中**任意相鄰兩位數字不同** (稱為「不重複數」)。例如 1101 重複 (相鄰 1,1)，1201 不重複。暴力遞增檢查在大數下極慢，本文提出 O(位數) 的貪心 + 進位演算法。

核心觀察

• 從低位向高位掃描，找到**第一對相鄰相同數字** (位置 i, i+1)。
• 在該位置進位 (將第 i 位 +1)，並將較低位 (0..i-1) 填入最小的「不重複」模式 (0101... 或 1010...)，即可得到答案。
• 進位可能觸發連鎖進位 (如 1999 → 2000)，需迴圈處理直到無重複為止。

演算法步驟

1. 將 N+1 分解為數字陣列 `digits[]` (低位在前)。
2. 函數 `search()`：從高位向低位掃描，返回第一個重複位置 `pos` (即 `digits[pos] == digits[pos+1]`)；無重複返回 -1。
3. 若 `pos == -1` → 當前數即為答案，重組返回。
4. 否則：`add_1(pos)` 將 `digits[pos]` 加 1 並處理進位；`clear(pos-1, 0)` 將較低位歸零。
5. 設定下一輪掃描上限 `end = pos`，重複步驟 2-4。
6. 最後將數字陣列重組為整數返回。

關鍵數據結構

typedef struct {
    unsigned char d[20]; // 足夠容納 64 位整數
    int top;             // 最高有效位索引
} Map;

完整 C 實作 (含測試主程式)

#include <stdio.h>

typedef struct { unsigned char d[20]; int top; } Map;

unsigned combi(const Map *m) {
    unsigned n = 0;
    for (int i = m->top; i >= 0; i--) n = n * 10 + m->d[i];
    return n;
}
void clear(Map *m, int from, int to) {
    for (int i = from - 1; i >= to; i--) m->d[i] = 0;
}
void add_1(Map *m, int from) {
    m->d[from]++;
    for (int i = from; i < m->top; i++) {
        m->d[i+1] += m->d[i] / 10;
        m->d[i] %= 10;
    }
    if (m->d[m->top] > 9) {
        m->d[m->top+1] = m->d[m->top] / 10;
        m->d[m->top++] %= 10;
    }
}
int search(const Map *m) {
    for (int i = m->top; i > 0; i--)
        if (m->d[i] == m->d[i-1]) return i - 1;
    return -1;
}
void parse(Map *m, unsigned n) {
    m->top = -1;
    while (n) { m->d[++m->top] = n % 10; n /= 10; }
}
unsigned find(unsigned n) {
    Map m; int end = 0, pos;
    parse(&m, n);
    while ((pos = search(&m)) > -1) {
        add_1(&m, pos);
        clear(&m, pos, end);
        end = pos;
    }
    return combi(&m);
}

int main() {
    for (unsigned i = 19922884; i < 19922885; i++)
        printf("%u %u\n", i, find(i + 1));
    return 0;
}

複雜度與優勢

• 時間：O(位數²) 最壞情況 (連續進位)，實際極快，位數 ≤ 19 時微秒級。
• 空間：O(1) 固定 20 位元組。
• 避免逐個檢查，直接構造答案，適合大整數 (64 位甚至大整數庫)。

此演算法展示了「從右向左掃描、就地進位、低位填最小模式」的通用技巧，可推廣至「無連續三位相同」、「特定數字不可相鄰」等變體問題。