C 語言生成 N 個不重複隨機數（0~N-1）：O(N²) 簡易版

需求

產生 N 個互不相同的隨機整數，範圍 [0, N-1]，用於測試演算法輸入資料。

演算法邏輯

1. 初始化結果陣列 a[N] 為 -1（標記未填入）。
2. count = 0 記錄已填入個數。
3. 迴圈直到 count == N：
   • 產生隨機數 temp = rand() % N。
   • 掃描 a[0..count-1]，若 temp 已存在 → 丟棄，重試。
   • 否則存入 a[count] = temp，count++。

完整程式碼

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_NUM 10

void random_n(int a[], int n);

int main() {
    int a[MAX_NUM], i = 0;
    while (i < MAX_NUM) a[i++] = -1;   // 關鍵初始化

    random_n(a, MAX_NUM);

    for (i = 0; i < MAX_NUM; ++i)
        printf("%d\t", a[i]);
    printf("\n");
    return 0;
}

void random_n(int a[], int n) {
    int temp, j, count = 0, flag;
    srand((unsigned)time(NULL));

    while (count < n) {
        temp = rand() % n;
        flag = 0;
        for (j = 0; j < count; ++j) {
            if (a[j] == temp) { flag = 1; break; }
        }
        if (!flag) {
            a[count++] = temp;
        }
    }
}

複雜度分析

• 最好：O(N)（每次隨機數皆不重複）。
• 最壞：O(N²)（後期重複機率高，大量重試）。
• 空間：O(N)（單一陣列）。

缺點與改進方向

當 N 較大（如 10⁵）時，重複檢查極慢。下一篇將介紹 O(N) 時間、雙陣列「洗牌法」，以空間換時間，彻底解決重複檢查瓶頸。

關鍵細節提醒

• srand(time(0)) 僅呼叫一次，放在函式開頭或 main。
• 陣列必須初始化（如 -1），否則殘留垃圾值導致誤判重複。
• rand() % n 有模數偏差（非均勻），嚴格場景需用拒絕採樣或 random() / C++11 <random>。