1102: 明明的随机数

解题思路:

去重：数组的去重是很难直接把重复值“删去”的，此题要求输入的随机数都是正整数，所以可以把重复值全改成0，最后输出非0数，就算去重了。

先排序，后去重。排序使用快速排序。

注意事项:

快速排序函数中，判断结束的标志是start >= end，不能写成start ==  end，debug时在这里卡了很久。

参考代码:

// 题目 1102: 明明的随机数

#include <iostream>

using namespace std;

void quickSort(int arr[], int start, int end); // 快速排序

void duplicateRemoval(int arr[], int len); // 去重并输出剩余元素个数

int main() {

    int N = 0; // 随机数个数

    cin >> N;

    int arr[N] = { 0 }; // 存储随机数

    for (int i = 0; i < N; i++) {

        cin >> arr[i];

    }

    quickSort(arr, 0, N - 1); // 先排序

    duplicateRemoval(arr, N); // 后去重

    for (int i = 0; i < N; i++) {

        if (arr[i]) {

            cout << arr[i] << " ";

        }

    }

    return 0;

}

void quickSort(int arr[], int start, int end) {

    // 这一步很关键，写成==都无法输出，因为到只剩1个元素时start == left，但传入参数为start和left - 1

    if (start >= end) {

        return;

    }

    int pivot = arr[start]; // 基准值

    int left = start; // 从左向右遍历找比pivot大的数

    int right = end;  // 从右向左遍历找比pivot小的数

    while (left < right) {

        while (left < right && arr[right] >= pivot) {

            right--; // 找到比pivot小的数

        }

        if (left < right) {

            arr[left] = arr[right]; // 移动到left位置，因为left的值已经传给pivot了

        }

        while (left < right && arr[left] <= pivot) {

            left++; // 找到比pivot大的数

        }

        if (left < right) {

            arr[right] = arr[left]; // 移动到right位置，因为right的值已经传给left了

        }

    }

    arr[left] = pivot; // left和right相遇，把基准值放到这里，至此就实现了左边都比pivot小，右边都比pivot大

    quickSort(arr, start, left - 1);

    quickSort(arr, right + 1, end);

}

void duplicateRemoval(int arr[], int len) {

    int count = len; // 剩余元素个数

    for (int i = 0; i < len - 1; i++) {

        if (arr[i] == arr[i + 1]) {

            arr[i] = 0; // 由于题目要求随机数均为正整数，所以归零就算是去重了

            count--;

        }

    }

    cout << count << endl; // 输出剩余个数

}