题解 | #明明的随机数#

#include <stdio.h>

void QuickSort(int x[], int left, int right){
    /*
    快速排序算法。
    */
    int begin = left;
    int end = right;
    int key = right;
    while(left < right){
        while(x[left] <= x[key] && left < right){
            left++;
        }
        while(x[right] >= x[key] && left < right){
            right--;
        }
        int temp = x[left];
        x[left] = x[right];
        x[right] = temp;
    }
    int temp = x[left];
    x[left] = x[key];
    x[key] = temp;
    if(left-1 > begin){
        QuickSort(x, begin, left-1);
    }
    if(left+1 < end){
        QuickSort(x, left+1, end);
    }
}

int main() {
    /*
    解题思路：首先使用哈希表读入非重复的元素，然后使用快速排序算法进行排序。
    */
    // 获得随机数的个数 N。
    int N;
    scanf("%d", &N);
    // 建立对应的哈希表读入非重复的元素。
    int Hash[1000];
    // 初始化哈希表。
    for(int i = 0; i < 1000; i++){
        Hash[i] = 0;
    }
    // 待排序序列。
    int x[N];
    int length = 0;
    // 读入随机数序列。
    int temp = 0;
    for(int i = 0; i < N; i++){
        scanf("%d", &temp);
        // 读入的这个数字在之前没有出现过。
        if(Hash[temp-1] == 0){
            Hash[temp-1] = 1;
            x[length++] = temp;
        }
    }
    // 快速排序。
    QuickSort(x, 0, length-1);
    for(int i = 0; i < length; i++){
        printf("%d\n", x[i]);
    }
    return 0;
}

这道题个人感觉主要是手搓快速排序比较难，如果使用更为简单但是时间复杂度更高的内部排序算法，例如冒泡排序等可能难度没有那么高。