JZTXT

PAT Basic 1045. 快速排序

发布时间 2023-03-22 21:17:02作者: 十豆加日月

PAT Basic 1045. 快速排序

1. 题目描述：

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

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

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

因此，有 3 个元素可能是主元。

2. 输入格式：

输入在第 1 行中给出一个正整数 \(N\)（≤\(10^5\)）； 第 2 行是空格分隔的 \(N\) 个不同的正整数，每个数不超过 \(10^9\)。

3. 输出格式：

在第 1 行中输出有可能是主元的元素个数；在第 2 行中按递增顺序输出这些元素，其间以 1 个空格分隔，行首尾不得有多余空格。

4. 输入样例：

5
1 3 2 4 5

5. 输出样例：

3
1 4 5

6. 性能要求：

Code Size Limit
16 KB
Java (javac)
Time Limit
800 ms
Memory Limit
64 MB
Other Compilers
Time Limit
200 ms
Memory Limit
64 MB

思路：

这道题卡了一下午。。。Google的题就是难一点？

最开始的想法是主元左边的元素都比它小，主元右边的元素都比它大，所以先统计出数组中的最小值和最大值的位置，那么主元只可能存在于最小值与最大值之间，然后遍历这其中的元素进行判断，但是这种做法造成testpoint1，3超时。后面想继续优化，就额外维持了两个变量leftMax和rigthMin减少耗时，但是testpoint1依然超时。。。

最后还是参考的大佬的题解：PAT-Basic-1045. 快速排序 – Lnyan's Blog (llonely.com)

因为主元的特殊性质，对原数组排序后，主元的位置是不会发生变化的，然后再额外增加一个leftMax判断条件保证筛选出真主元即可。

eg1： 3 1 2 4 6 5（排序前） 1 2 3 4 5 6（排序后），4是真主元。

eg2： 3 1 6 4 2 5（排序前） 1 2 3 4 5 6（排序后），4是假主元。

另外就是输出时发现printf("%c%d", (i==0?'\0':' '), pRes[i]); // must print '\0' for null character如果先打印出一个空字符的话，后续内容是不会输出的，应该是printf()的某种机制。

My Code:

// // testpoint1, 3: Time Limit Exceeded
// #include <stdio.h>
// #include <stdlib.h> // malloc header
// #include <stdbool.h> // bool header

// bool pivotJudge(const int *array, int len, int index);

// int main(void)
// {
//     int numAll = 0;
//     int *pInt = NULL;
//     int i=0;
//     int minIndex = 0, maxIndex = 0;
//     int activeCount = 0; // the candidate maximum count
//     int *pRes = NULL;
//     int resCount = 0;
    
//     scanf("%d", &numAll);
    
//     pInt = (int *)malloc(sizeof(int) * numAll);
    
//     for(i=0; i<numAll; i++) // the number is all different
//     {
//         scanf("%d", pInt+i);
//         if(pInt[i]<pInt[minIndex])
//         {
//             minIndex = i;
//         }
//         if(pInt[i]>pInt[maxIndex])
//         {
//             maxIndex = i;
//         }
//     }
    
//     activeCount = maxIndex - minIndex + 1;
//     pRes = (int *)malloc(sizeof(int) * activeCount);
    
//     for(i=minIndex; i<=maxIndex; i++) // judge pivot for each element
//     {
//         if(pivotJudge(pInt, numAll, i))
//         {
//             pRes[resCount++] = pInt[i];
//         }
//     }
    
//     printf("%d\n", resCount);
//     for(i=0; i<resCount; i++)
//     {
// //         printf("%d", pRes[i]);
// //         printf("%c%d", (i==0?'\0':' '), pRes[i]); // must print '\0' for null character
//         if(i==0)
//             printf("%d", pRes[i]);
//         else
//             printf(" %d", pRes[i]);
//     }
//     printf("\n");
    
//     free(pInt);
//     free(pRes);
//     return 0;
// }

// bool pivotJudge(const int *array, int len, int index)
// {
//     int i = 0;
//     for(i=0; i<index; i++)
//     {
//         if(array[i] > array[index])
//         {
//             return false;
//         }
//     }
    
//     for(i=index+1; i<len; i++)
//     {
//         if(array[i] < array[index])
//         {
//             return false;
//         }
//     }
    
//     return true;
// }

// // testpoint1: Time Limit Exceeded
// #include <stdio.h>
// #include <stdlib.h> // malloc header
// #include <stdbool.h> // bool header

// //bool pivotJudge(const int *array, int len, int minIndex, int maxIndex, int index);
// void findLR_Extrem(const int *array, int len, int minIndex, int maxIndex, int *leftMax, int *rightMin);
// void findRightMin(const int *array, int len, int index, int *rightMin);

// int main(void)
// {
//     int numAll = 0;
//     int *pInt = NULL;
//     int i=0;
//     int minIndex = 0, maxIndex = 0;
//     int activeCount = 0; // the candidate maximum count
//     int *pRes = NULL;
//     int resCount = 0;
//     int leftMax = 0, rightMin = 0;
    
    
//     scanf("%d", &numAll);
    
//     pInt = (int *)malloc(sizeof(int) * numAll);
    
//     for(i=0; i<numAll; i++) // the number is all different
//     {
//         scanf("%d", pInt+i);
//         if(pInt[i]<pInt[minIndex])
//         {
//             minIndex = i;
//         }
//         if(pInt[i]>pInt[maxIndex])
//         {
//             maxIndex = i;
//         }
//     }
    
//     activeCount = maxIndex - minIndex + 1;
//     pRes = (int *)malloc(sizeof(int) * activeCount);
    
//     findLR_Extrem(pInt, numAll, minIndex, minIndex, &leftMax, &rightMin);
//     //findLR_Extrem(pInt, numAll, minIndex, maxIndex, &leftMax, &rightMin);

//     // testpoint3, 4 wrong answer. this solution is wrong, eg. 3 1 5 2 4 6
// //     for(i=minIndex; i<maxIndex; i++)
// //     {
// //         if(pInt[i] > pInt[i+1])
// //         {
// //             pInt[i] = pInt[i+1] = 0;
// //             ++i;
// //         }
// //     }
    
// //     printf("minIndex: %d, maxIndex: %d\n", minIndex, maxIndex);
// //     printf("pInt[-1]: %d\n", pInt[-1]);
    
//     for(i=minIndex; i<=maxIndex; i++) // judge pivot for each element
//     {
//         if(i>0 && pInt[i-1]>leftMax)
//             leftMax = pInt[i-1];
//         if(pInt[i] == rightMin && i<numAll-1)
//             findRightMin(pInt, numAll, i+1, &rightMin);
        
//         if(pInt[i]>=leftMax && pInt[i]<=rightMin)
//         {
//             pRes[resCount++] = pInt[i];
//         }
//     }
    
// //     for(i=minIndex; i<=maxIndex; i++) // judge pivot for each element
// //     {
// //         if(pInt[i]>=leftMax && pInt[i]<=rightMin && pivotJudge(pInt, numAll, minIndex, maxIndex, i))
// //         {
// //             pRes[resCount++] = pInt[i];
// //         }
// //     }
    
//     printf("%d\n", resCount);
//     for(i=0; i<resCount; i++)
//     {
// //         printf("%d", pRes[i]);
// //         printf("%c%d", (i==0?'\0':' '), pRes[i]); // must print '\0' for null character
//         if(i==0)
//             printf("%d", pRes[i]);
//         else
//             printf(" %d", pRes[i]);
//     }
//     printf("\n");
    
//     free(pInt);
//     free(pRes);
//     return 0;
// }

// // bool pivotJudge(const int *array, int len, int minIndex, int maxIndex, int index)
// // {
// //     int i = 0;
// //     for(i=minIndex; i<index; i++)
// //     {
// //         if(array[i] > array[index])
// //         {
// //             return false;
// //         }
// //     }
    
// //     for(i=index+1; i<=maxIndex; i++)
// //     {
// //         if(array[i] < array[index])
// //         {
// //             return false;
// //         }
// //     }
    
// //     return true;
// // }

// void findLR_Extrem(const int *array, int len, int minIndex, int maxIndex, int *leftMax, int *rightMin)
// {
//     int i=0;
    
//     *leftMax = array[0];
//     *rightMin = array[len-1];
    
//     for(i = 1; i < minIndex; i++)
//     {
//         if(array[i] > *leftMax)
//         {
//             *leftMax = array[i];
//         }
//     }
    
//     for(i=len-2; i > maxIndex; i--)
//     {
//         if(array[i] < *rightMin)
//         {
//             *rightMin = array[i];
//         }
//     }
// }

// void findRightMin(const int *array, int len, int index, int *rightMin)
// {
//     int i = 0;
//     *rightMin = array[index];
    
//     for(i=index+1; i<len; i++)
//     {
//         if(array[i] < *rightMin)
//         {
//             *rightMin = array[i];
//         }
//     }
// }


// refer to http://www.llonely.com/pat-b-1045-quicksort/
#include <stdio.h>
#include <stdlib.h> // qsort header

int cmp(const void * p1, const void * p2);

int main(void)
{
    int numAll = 0;
    int *pInt = NULL;
    int i=0;
    int *pRes = NULL;
    int resCount = 0;
    int *pTemp = NULL;
    int leftMax = 0;
    
    scanf("%d", &numAll);
    
    pInt = (int *)malloc(sizeof(int) * numAll);
    pTemp = (int *)malloc(sizeof(int) * numAll);
    pRes = (int *)malloc(sizeof(int) * numAll);
    
    for(i=0; i<numAll; i++) // the number is all different
    {
        scanf("%d", pInt+i);
        pTemp[i] = pInt[i];
    }
    
    //void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))
    qsort(pTemp, numAll, sizeof(int), cmp);
    
    leftMax = pInt[0];
    
    for(i=0; i<numAll; i++)
    {
        if(i>0 && pInt[i-1]>leftMax)
        {
            leftMax = pInt[i-1];
        }
        if(pInt[i]==pTemp[i] && pInt[i]>=leftMax)
        {
            pRes[resCount++] = pInt[i];
        }
    }
    
    printf("%d\n", resCount);
    for(i=0; i<resCount; i++)
    {
//         printf("%d", pRes[i]);
//         printf("%c%d", (i==0?'\0':' '), pRes[i]); // must print '\0' for null character
        if(i==0)
            printf("%d", pRes[i]);
        else
            printf(" %d", pRes[i]);
    }
    printf("\n");
    
    free(pInt), free(pTemp), free(pRes);
    
    return 0;
}

int cmp(const void * p1, const void * p2)
{
    return (*(int *)p1 - *(int *)p2);
}