写一个C语言的程序，快速从100万个数中抽取2万个不同的数

以下是一个 C 语言程序，可以快速从100万个数中抽取2万个不同的数：

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

#define TOTAL_NUMS 1000000
#define SELECTED_NUMS 20000

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int main() {
    int selected[SELECTED_NUMS];
    srand(time(NULL)); // 设置随机种子

    // 首先将前2万个数选中
    for (int i = 0; i < SELECTED_NUMS; i++) {
        selected[i] = i + 1;
    }

    // 然后从第2万个数开始，以一定的概率替换已选中的数
    for (int i = SELECTED_NUMS; i < TOTAL_NUMS; i++) {
        int r = rand() % i + 1; // 生成一个随机数
        if (r <= SELECTED_NUMS) {
            selected[r - 1] = i + 1;
        }
    }

    // 输出结果
    printf("Selected numbers: ");
    for (int i = 0; i < SELECTED_NUMS; i++) {
        printf("%d ", selected[i]);
    }
    return 0;
}

这个程序的思路是，首先将前2万个数选中，然后从第2万个数开始，以一定的概率替换已选中的数。具体来说，对于第 i 个数，以 2万/i 的概率替换已选中的数（其中 i > 2万）。这个概率的计算方法是，每个数都有 2万/i 的概率被选中，因此最终被选中的概率就是 2万/i。

这个程序的时间复杂度为 O(n)，因此可以快速地从100万个数中抽取2万个不同的数。