一觉睡到小时候


私信TA

用户名:ldxx32

访问量:1141

签 名:

这个名字真的有十个字

等  级
排  名 1744
经  验 2532
参赛次数 9
文章发表 6
年  龄 99
在职情况 学生
学  校 林煜轩
专  业 游戏

  自我简介:

没有什么困难是战胜不了我的。

TA的其他文章

解题思路:


去重:数组的去重是很难直接把重复值“删去”的,此题要求输入的随机数都是正整数,所以可以把重复值全改成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; // 输出剩余个数

}


 

0.0分

1 人评分

  评论区