题目

1045 快速排序 （25 分）
著名的快速排序算法里有一个经典的划分过程：我们通常采用某种方法取一个元素作为主元，通过交换，把比主元小的元素放到它的左边，比主元大的元素放到它的右边。 给定划分后的 N 个互不相同的正整数的排列，请问有多少个元素可能是划分前选取的主元？
例如给定 , 排列是1、3、2、4、5。则：
1 的左边没有元素，右边的元素都比它大，所以它可能是主元；
尽管 3 的左边元素都比它小，但其右边的 2 比它小，所以它不能是主元；
尽管 2 的右边元素都比它大，但其左边的 3 比它大，所以它不能是主元；
类似原因，4 和 5 都可能是主元。
因此，有 3 个元素可能是主元。
输入格式：
输入在第 1 行中给出一个正整数 N（≤10的5次方）；
第 2 行是空格分隔的 N 个不同的正整数，每个数不超过 10的9次方
输出格式：
在第 1 行中输出有可能是主元的元素个数；在第 2 行中按递增顺序输出这些元素，其间以 1 个空格分隔，行首尾不得有多余空格。
输入样例：
5
1 3 2 4 5
输出样例：
3
1 4 5

分析

这条题，按照我做题原则，先好好思考，整理逻辑，实在不行再参考别人。
一开始感觉应该挺简单，首先排除暴力分析，用步进分析法+双指针应该可以一次循环搞掂。
可是做着做着，我用一些测试用例通不过，发现这个逻辑有漏洞，这一分析，发现更多种情况要填要弥补，my god
对于我来说，思考太久一直是我弱项，可能没有写草稿的习惯，后来我尝试通过用例来弥补各种情况的逻辑编写

（请大家不吝赐教一些快速思路。）

最后也发现这样写完后也顺利一次通过。
然后再去看看别人写的，除了我们最后输出的思路一样，但在处理上他们基本上用STL封装好的排序sort，或者结合reverse。我才知道我们思考的区别，因为根据快速排序的主元特性，我一开始觉得没必要去排序或者再增加空间再来筛选，它已经就是按照原样进来。

主题思路

辅助空间：nums保存主元的数组，pre指针保存前一个主元，cur指针当前接收的值，minValue遇过的历史最小值，maxValue遇过的历史最大值
过程：（就是逻辑的暴解）
1.循环每一个进来的值
1.1判断 pre是否小于cur
当前值是否大于上一个主元的值，是就进入与历史最大值或最小值比较的判断
1.2如果pre==cur
与历史最大值，历史最小值比较

这就是我写的其中一些用例分析思路

一种情况
1 3 5 1000  //pre=2 cur =3,min =1,max =1000，只需要变化pre = cur,cur++
1 3 5 1000 7 //pre =3,cur =4,min =1 ,max=1000,明显nums[cur]<nums[pre],这两个不能要，MULength-=2，最后pre要退却一位即pre--,cur=pre+1;
1 3 5 1000(作废) 7(作废) 9 //pre =2 ,cur = 3,虽然符合nums[cur]>nums[pre]，但历史中出现过最大值1000，你的cur的值还是不能要，继续cur = pre+1，pre不变
1 3 5 1000(作废) 7(作废) 9(作废) 2. //pre =2 ,cur = 3,明显nums[cur]>nums[pre],这两个不能要,MULength-=2,最后pre要退却一位即pre--,cur=pre+1;
最后结果是1 3 5(作废) 1000(作废) 7(作废) 9(作废) 2(作废)，但是这个1和3结果明显不能接受，明显3不能要，需要改写，尝试用局部循环判断nums[cur]<nums[pre],直到把pre退却到适合的位置

另一种情况
2 3 5 1000  //pre=2 cur =3,min =2,max =1000，只需要变化pre = cur,cur++
2 3 5 1000 1//pre =3,cur =4,min =2 ,max=1000，明显nums[cur]<nums[pre]，再发现nums[cur]比历史最小值还要小，前面所有作废，这里就要pre与cur重置了，cur =pre=0,nums[0]=nums[cur],更新一下MULength-cur
2(作废) 3(作废) 5(作废) 1000(作废) 1(作废)

另一种情况
2 1 //pre =0,cur =1,min=2,max=2;明显nums[cur]<nums[pre],这两个不能要，MULength-=2,最后pre要退却一位即pre--, 若是pre退无可退，也就是负值，设置pre=cur = 0,否则cur=pre+1;

代码

#include <stdio.h>
#define MAX_NUM 100000
#define MAX_INT 0x7fffffff
unsigned int GetInputToInt();
int main()
{
    //nums用来放入数据，N是输入个数， MULength是主元个数长度 
    int nums[MAX_NUM]={0},i=0,N,MULength =0;
    //处理输入
    //例子：2 4 3 1 5 ，只有5才是主元 
    //例子：4 5 6 2 1 8 7 9 3 10   只有10才是主元   用于这个测试点，发现我第一个版本错了，漏了判决 
    MULength = N = GetInputToInt();
    
    //处理与控制：采用双指针控制
    int prePos=0,curPos=0,curMinValue=MAX_INT,curMaxValue=0;
    for(;i<N;i++)
    {
        nums[curPos] = GetInputToInt();
        //（尝试步进分析，一旦遇到前者大于后者，马上重置prePos，剔除该两个，因为都不可能是主元了，
        //1还保留一直遇到过的最小值curMinValue，和遇到过的最大值curMaxValue） 
        if(prePos<curPos)
        {
            //1.1若当前值大不过上一个值 
            if(nums[prePos]>nums[curPos])
            {
                //（作废情况）
                //1.3看看是否遇上了比当前最小值还要小的当前值 
                if(curMinValue>nums[curPos])
                {
                    //1.3.1 要是发现历史最小值都比不过当前值小，OK，前面全部作废 
                    curMinValue = nums[curPos];
                    //更新MULength，这里分开写，让可读性好点 
                    MULength = MULength - curPos;//前面作废，有多少个，curPos个(curPos是下标，curPos-1就是个数) 
                    MULength--; //再减去当前第curPos那一个 
                    prePos = curPos = 0; 
                } 
                else
                {
                    MULength-=2;//当前这两个肯定不要了(pre与cur）
                    --prePos;
                    //1.3.2 要是发现前面最小值依然坚挺能接受考验。 需要把prePos退却到刚好nums[curPos]>nums[pre]的位置上
                    while(prePos>=0&&nums[curPos]<nums[prePos])
                    {
                        prePos--;
                        MULength--;
                    }
                    if(prePos<0)
                    //什么情况下会来到这里,应该没有，因为有1.3.1过滤了，最小值是来不了  例如，6(作废) 1(作废) 5(作废) 3 ，但pre=0.cur=0,明显，这个例子来不了 ，希望能找到例外 
                        prePos = curPos = 0; 
                    else
                    //来到这里，就是已经找到刚好 nums[curPos]>nums[pre]的位置上，重置curPos 
                        curPos = prePos+1; 
                }   
            }
            //1.2要是比得过，接下来看情况看下是否更新一下最大值 
            else
            {
                //（正常情况） 看看是否遇上了比历史最大值还要大的当前值
                if(curMaxValue<nums[curPos])
                {
                    curMaxValue = nums[curPos];//保留 
                    prePos = curPos;
                    curPos++; 
                }
                //若然当前值比不上历史最大值 
                else
                {//（作废情况）
                //这种情况就好像1，1000，2，3，4，此时cur=4,pre=3,虽然符合pre<pos,但是前面出现过巨无霸1000，在巨无霸后面到当前值都得作废，除非出现过比巨无霸还要猛的。
                    MULength = MULength -1;//减一就是当前cur的值不要了 
                    curPos = prePos+1; //更新下一次应该要填的位置 
                    //prePos = curPos = 0; 
                }    
            }
            
        }
        //2. 一般进入这里的情况都是，初始化，或者是前面都失效的情况下。
        else if(prePos==curPos)//
        {
            //看情况更新最大值与最小值 
            //2.1 
            if(curMaxValue<nums[curPos])
                curMaxValue = nums[curPos];
            else
            {//若是连历史最大值都大不上，也就是当前值作废  如 20(作废) 10(作废) 15 ，历史最小值是10 
                MULength--;
                prePos = curPos = 0;
                continue;
            }
            
            //2.2
            if(curMinValue>nums[curPos])
                //遇上了比历史最小值还小的值，更新 。如 2(作废) 3(作废) 1 ，历史最小值是2 
                curMinValue = nums[curPos]; 
            else
            {//若是连历史最小值都小不过. 如 20(作废) 10(作废) 21 ，历史最小值是10；如果是  20(作废) 10(作废) 15 ，这个有2.1过滤，不会来到这里 
                //不用操作 ， 
            }
            
            prePos = curPos++;
        }
    }
    //2. 输出
    printf("%d\n",MULength);
    for(i=0;i<MULength-1;i++)
        printf("%d ",nums[i]);
    if(i==MULength-1)
        printf("%d",nums[i]);
    putchar('\n');
    return 0; 
}

unsigned int GetInputToInt()
{
    char c;
    unsigned int sum =0;
    while((c=getchar())!=EOF&&c!=' '&&c!='\n')
        sum = sum*10+c-'0';
    return sum;
}