PAT-B 1045. 快速排序

原题

著名的快速排序算法里有一个经典的划分过程：我们通常采用某种方法取一个元素作为主元，通过交换，把比主元小的元素放到它的左边，比主元大的元素放到它的右边。给定划分后的N个互不相同的正整数的排列，请问有多少个元素可能是划分前选取的主元？

例如给定N = 5, 排列是1、3、2、4、5。则：

1的左边没有元素，右边的元素都比它大，所以它可能是主元；
尽管3的左边元素都比它小，但是它右边的2它小，所以它不能是主元；
尽管2的右边元素都比它大，但其左边的3比它大，所以它不能是主元；
类似原因，4和5都可能是主元。
因此，有3个元素可能是主元。

输入样例：

1 3 2 4 5

输出样例：

1 4 5

看到这个题目之后第一时间想到快排枢轴划分，用一个函数判断表中的一个元素是否为主元：

bool partition(const int L[], int N, int pivo) {
    bool flag = 1;
    int low = 0, high = N - 1;
    while (flag && low < pivo) {
        if (L[low] > L[pivo]) {
            flag = 0;
        }
        low++;
    }
    while (flag && high > pivo) {
        if (L[high] < L[pivo]) {
            flag = 0;
        }
        high--;
    }
    return flag;
}

仔细想想这个方法有明显缺陷，每个元素都判断一次的话复杂度是O(n²)，明显会超时。试提交一下果然很轻松地超时了。

参考算法笔记整理一下问题
其实这一题跟快速排序没有一毛钱关系。输入一个有N个整数的序列，如果第i个数的左边所有数都比它小，右边所有数都比它大，则这个数就是主元。

解决思路：
输入序列为L，设数组leftMax、rightMin。leftMax[i]为L[0]~L[i-1]的最大值。rightMin[i]为L[i+1]~L[N-1]的最小值。遍历两次L获得leftMax和rightMin。最后，如果L[i]>leftMax[i]且L[i]<rightMin[i]，则L[i]就是所求主元。

代码

int main() {
    int N;
    cin >> N;
    int L[100010], ans[100010];
    int leftMax[100010], rightMin[100010];
    int count = 0;
    for (int i = 0; i < N; i++) {
        cin >> L[i];
    }

    leftMax[0] = 0;
    for (int i = 1; i < N; i++) {
        if (L[i - 1] > leftMax[i - 1]) {
            leftMax[i] = L[i - 1];
        }
        else {
            leftMax[i] = leftMax[i - 1];
        }
    }

    rightMin[N - 1] = 0x3fffffff;
    for (int i = N - 2; i >= 0; i--) {
        if (L[i + 1] < rightMin[i + 1]) {
            rightMin[i] = L[i + 1];
        }
        else {
            rightMin[i] = rightMin[i + 1];
        }
    }

    for (int i = 0; i < N; i++) {
        if (L[i] > leftMax[i] && L[i] < rightMin[i]) {
        ans[count++] = L[i];
        }
    }
    cout << count << endl;
    for (int i = 0; i < count; i++) {
        if (i) {
            cout << ' ';
        }
        cout << ans[i];
    }
    cout << endl;
    return 0;
}

这道题有一个坑就是，当输入主元个数为0时，输出第二行必须输出一个换行。