PAT-BASIC1045——快速排序/PAT-ADVANCED1101——Quick Sort

我的PAT-BASIC代码仓：https://github.com/617076674/PAT-BASIC

我的PAT-ADVANCED代码仓：https://github.com/617076674/PAT-ADVANCED

原题链接：

PAT-BASIC1045:https://pintia.cn/problem-sets/994805260223102976/problems/994805278589960192

PAT-ADVANCED1101:https://pintia.cn/problem-sets/994805342720868352/problems/994805366343188480

题目描述：

PAT-BASIC1045:

PAT-ADVANCED1101:

知识点：快速排序

思路：先排序，寻找和排序后数组相同的数字

对于快排而言，题目所述的主元的位置就是其排序后的最终位置。

所以如果该元素是主元，那么一定满足其位置和排序后的数组中的位置相同。但是仅仅满足这一点是不够的，对于[3, 2, 1]这样的序列，2的位置就是排序后的最终位置，但2并不是一个主元。我们还需满足一个条件：对于索引为i的主元，数组中索引在[0, i - 1]位置的最大值需要小于索引在i位置的值。

这个条件很容易用反证法证明。假设索引为i的位置不是一个主元。根据条件，[0, i - 1]位置的值均小于i位置的值，那么i之后的索引一定存在小于i位置的值。但是根据最开始的条件，该位置和排序后的数组中的位置相同。所以比i小的值有且仅有i个，恰好等于[0, i - 1]中的元素数量，所以i之后的索引不可能小于i位置的值。得出矛盾。所以满足这两个条件，就是主元。

时间复杂度是O(nlogn)，其中n为输入的数组大小。空间复杂度是O(m)，其中m为可能的主元数。

本题有一个坑点：

当主元数为0时，需要输出一个空行，否则测试点2会报格式错误。

错误思路：

我一开始的思路是从头和从尾分别比较排序后的数组和输入数组中的元素是否相等，将相等的元素看作是主元，一旦发现不相等的元素就停止搜索。但是我这么做忽略了这么一种情况[1, 3, 2, 4, 6, 5, 7]，根据我的思路我只能得到[1, 7]是主元，而忽略了主元4。测试点5就是这样一组测试用例。

C++代码：

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
	int count;

	cin >> count;

	long tempNum;
	vector<long> beforeSort;
	vector<long> afterSort;
	vector<long> result;

	for (int i = 0; i < count; i++) {
		cin >> tempNum;
		beforeSort.push_back(tempNum);
		afterSort.push_back(tempNum);
	}

	sort(afterSort.begin(), afterSort.end());

	int max = 0;
	for (int i = 0; i < afterSort.size(); i++) {
		if (afterSort[i] == beforeSort[i] && afterSort[i] > max) {
			result.push_back(afterSort[i]);
		}
		if (beforeSort[i] > max) {
			max = beforeSort[i];
		}
	}

	cout << result.size() << endl;
	for (int i = 0; i < result.size(); i++) {
		cout << result[i];
		if (i != result.size() - 1) {
			cout << " ";
		}
	}
	printf("\n");
}

C++解题报告：