字符串刪除指定字符：哈工大機試真題雙算法實現與複雜度分析

字符串中刪除指定字符：兩種經典算法對比

哈爾濱工業大學2009年計算機研究生機試真題：輸入字符串s和字符c，刪除s中所有c，輸出結果。多組測試數據，EOF結束。

樣例

輸入:
heallo
a

輸出:
hello

解法一：雙數組法 (O(n)時間，O(n)空間)

#include <stdio.h>

int main() {
    char arr[200], arrNew[200];
    char focus;
    
    while (scanf("%s", arr) != EOF) {
        getchar();  // 關鍵：消耗scanf留下的換行符，否則%c讀到換行符
        scanf("%c", &focus);
        
        int j = 0;
        for (int i = 0; arr[i] != '\0'; i++) {
            if (arr[i] != focus) {
                arrNew[j++] = arr[i];
            }
        }
        arrNew[j] = '\0';
        printf("%s\n", arrNew);
    }
    return 0;
}

關鍵點

• getchar()消耗換行符：scanf("%s")讀完字符串後停在換行符，後續%c會直接讀到換行符導致邏輯錯誤
• 雙緩衝區思路清晰，不修改原數組，適合需要保留原數據的場景
• 時間復雜度O(n)，空間復雜度O(n)

解法二：原地覆蓋法 (O(n)時間，O(1)空間)

#include <stdio.h>
#include <string.h>

int main() {
    char arr[200];
    char focus;
    
    while (scanf("%s", arr) != EOF) {
        int m = strlen(arr);
        getchar();  // 消耗換行符
        scanf("%c", &focus);
        
        for (int i = 0; i < m; i++) {
            if (arr[i] == focus) {
                /* 將後續字符前移一位覆蓋當前字符 */
                for (int j = i + 1; j < m; j++) {
                    arr[j - 1] = arr[j];
                }
                i--;      // 當前位置已被新字符填充，需重新檢查
                arr[m-1] = '\0';  // 字符串長度-1，補終止符
                m--;      // 有效長度減1
            }
        }
        printf("%s\n", arr);
    }
    return 0;
}

關鍵邏輯解析

1. 發現目標字符時，啟動內層循環將[i+1, m-1]區間整體前移一位
2. i--：因為前移後arr[i]位置是新字符(原arr[i+1])，必須重新判斷
3. arr[m-1] = '\0'：原字符串最後一位是\0，長度減1後需將新末尾設為\0
4. m--：有效長度遞減，縮小後續掃描範圍

複雜度對比與選擇建議

優化版原地算法：雙指針單次掃描 O(n)時間 O(1)空間

void remove_char_opt(char *str, char c) {
    char *read = str, *write = str;
    while (*read) {
        if (*read != c) {
            *write++ = *read;  // 非目標字符：寫入並推進寫指針
        }
        read++;  // 讀指針始終推進
    }
    *write = '\0';  // 截斷尾部
}

/* 調用示例 */
while (scanf("%s", arr) != EOF) {
    getchar();
    scanf("%c", &focus);
    remove_char_opt(arr, focus);
    printf("%s\n", arr);
}

雙指針優勢

• 單次遍歷，無嵌套循環，嚴格O(n)
• 無數據搬移開銷，每個字符最多被讀寫一次
• 代碼極其簡潔，易於驗證正確性
• C++ STLstd::remove即採用此算法

邊界測試用例

/* 測試數據 */
"aaaaa", 'a'        → "" (全刪除)
"hello", 'x'        → "hello" (無目標字符)
"", 'a'             → "" (空字符串)
"abacada", 'a'      → "bcd" (多次刪除)
"a", 'a'            → "" (單字符刪除)
"abc", 'c'          → "ab" (末尾刪除)

總結

機試中雙數組法寫得最快、錯誤率最低；面試/工程中雙指針法是標準答案。理解getchar()處理換行符的必要性，是scanf/%c組合輸入的核心考點。掌握三種解法的時空權衡，才能根據具體約束(內存限制、數據可變性、性能要求)做出最優選擇。