OJ題解：元素插入 - 面試隊列插隊模擬

題目情境

模擬面試隊列：原有 N 人編號序列，Mr.true 拿到編號 P，插入第 Q 個位置 (1-based)。輸出新序列。

演算法：陣列後移

1. 讀入原序列至陣列 a[0..N-1]
2. 插入位置 pos = Q-1 (0-based)
3. 從尾端向前搬移：for(i=N; i>pos; i--) a[i] = a[i-1]
4. a[pos] = P
5. 輸出 a[0..N] (新長度 N+1)

完整原始碼

#include <stdio.h>

int main() {
    int T, N, P, Q, a[10001];
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &N);
        for (int i = 0; i < N; i++) scanf("%d", &a[i]);
        scanf("%d %d", &P, &Q);
        int pos = Q - 1;
        for (int i = N; i > pos; i--) a[i] = a[i-1];
        a[pos] = P;
        for (int i = 0; i <= N; i++) {
            printf("%d", a[i]);
            if (i < N) printf(" ");
        }
        if (T) printf("\n");
    }
    return 0;
}

原代碼問題分析

• 原代碼用複雜的雙層迴圈與暫存變數 t,k 嘗試原地輪轉，邏輯錯誤且難懂
• 正確做法：從後向前單向搬移，一次賦值，無需暫存

範例追蹤

輸入: N=3, 序列=1 2 3, P=4, Q=2
pos=1
搬移: a[3]=a[2]=3, a[2]=a[1]=2
插入: a[1]=4
結果: 1 4 2 3 ✓

複雜度