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; // 输出剩余个数
}