526互联

PAT Basic 1075. 链表元素分类

发布时间 2023-04-08 22:33:19作者: 十豆加日月

PAT Basic 1075. 链表元素分类

1. 题目描述：

给定一个单链表，请编写程序将链表元素进行分类排列，使得所有负值元素都排在非负值元素的前面，而 [0, K] 区间内的元素都排在大于 K 的元素前面。但每一类内部元素的顺序是不能改变的。例如：给定链表为 18→7→-4→0→5→-6→10→11→-2，K 为 10，则输出应该为 -4→-6→-2→7→0→5→10→18→11。

2. 输入格式：

每个输入包含一个测试用例。每个测试用例第 1 行给出：第 1 个结点的地址；结点总个数，即正整数N (\(≤10^5\))；以及正整数K (\(≤10^3\))。结点的地址是 5 位非负整数，NULL 地址用 \(−1\) 表示。

接下来有 N 行，每行格式为：

Address Data Next

其中 Address 是结点地址；Data 是该结点保存的数据，为 \([−10^5,10^5]\) 区间内的整数；Next 是下一结点的地址。题目保证给出的链表不为空。

3. 输出格式：

对每个测试用例，按链表从头到尾的顺序输出重排后的结果链表，其上每个结点占一行，格式与输入相同。

4. 输入样例：

00100 9 10
23333 10 27777
00000 0 99999
00100 18 12309
68237 -6 23333
33218 -4 00000
48652 -2 -1
99999 5 68237
27777 11 48652
12309 7 33218

5. 输出样例：

33218 -4 68237
68237 -6 48652
48652 -2 12309
12309 7 00000
00000 0 99999
99999 5 23333
23333 10 00100
00100 18 27777
27777 11 -1

6. 性能要求：

Code Size Limit
16 KB
Time Limit
400 ms
Memory Limit
64 MB

思路：

定义结构体Node表示链表中的结点，开始的想法是先根据地址找出原始链表，然后因为这里要分为三类并且每一类内部的顺序是按照原始链表的，所以在结构体Node中定义元素class和order分别记录类别和原始顺序，最后调用库函数qsort对原始链表进行排序和输出。第一次提交时testpoint5报time limit exceeded，对代码进行优化时，发现不需要用qsort对原始链表进行排序，分三次遍历链表并根据条件输出即可，改过来后testpoint5仍然报time limit exceeded。。。

感觉无法进行优化了，无奈只能参考大佬代码：1075. 链表元素分类(25)-PAT乙级真题_柳婼的博客-CSDN博客 ，是直接根据结点地址最大值分配结构体数组，这样可以做到随机访问，本质上还是用空间换时间，所以主要耗时其实在于根据地址找出原始链表。。。

My Code:

// first way
// #include <stdio.h>
// #include <stdlib.h> // malloc header, qsort header

// typedef struct node
// {
//     int address;
//     int data;
//     int next;
//     int class; // group into 3 class, 1 means negative, 2 means less than K, 3 means others
//     int order; // to record order of original linkList
// } Node;

// int myCmp(const void *p1, const void *p2);

// // first submit testpoint5 time limit exceeded
// int main(void)
// {
//     int pHead=0, nodeCount=0, numK=0;
//     int i=0; //iterator
//     Node *linkList = NULL;
//     Node *validLink = NULL;
//     int validNodeCount = 0;
    
//     scanf("%d%d%d", &pHead, &nodeCount, &numK);
//     linkList = (Node *)malloc(sizeof(Node) * nodeCount);
//     validLink = (Node *)malloc(sizeof(Node) * nodeCount);
    
//     for(i=0; i<nodeCount; ++i)
//     {
//         scanf("%d%d%d", &linkList[i].address, &linkList[i].data, &linkList[i].next);
        
//         if(linkList[i].data < 0) // set weight
//         {
//             linkList[i].class = 1;
//         }
//         else if(linkList[i].data <= numK)
//         {
//             linkList[i].class = 2;
//         }
//         else
//         {
//             linkList[i].class = 3;
//         }
        
        
//         if(linkList[i].address == pHead) // first element
//         {
//             validLink[validNodeCount++] = linkList[i];
//             validLink[validNodeCount-1].order = validNodeCount; // set order
//         }
        
//         if(validNodeCount && linkList[i].address == validLink[validNodeCount-1].next) // find next node
//         {
//             validLink[validNodeCount++] = linkList[i];
//             validLink[validNodeCount-1].order = validNodeCount; // set order
//         }
//     }
    
//     while(validLink[validNodeCount-1].next != -1) // to find all node on the linkList
//     {
//         for(i=0; i<nodeCount; ++i)
//         {
//             if(validLink[validNodeCount-1].next == -1) break;
            
//             if(linkList[i].address == validLink[validNodeCount-1].next) // find next node
//             {
//                 validLink[validNodeCount++] = linkList[i];
//                 validLink[validNodeCount-1].order = validNodeCount; // set order
//                 break;
//             }
//         }
//     }
    
// //     for(i=0; i<validNodeCount; ++i) // traverse original linkList to set weight
// //     {
// //         if(validLink[i].data < 0)
// //         {
// //             validLink[i].class = 1;
// //         }
// //         else if(validLink[i].data <= numK)
// //         {
// //             validLink[i].class = 2;
// //         }
// //         else
// //         {
// //             validLink[i].class = 3;
// //         }
        
// //         validLink[i].order = i;
// //     }
    
// //     for(i=0; i<validNodeCount; ++i) // output weight
// //     {
// //         printf("class: %d, order: %d\n", validLink[i].class, validLink[i].order);
// //     }
    
//     qsort(validLink, validNodeCount, sizeof(Node), myCmp);
    
//     for(i=0; i<validNodeCount-1; ++i) // alter next address and output
//     {
//         validLink[i].next = validLink[i+1].address;
//         printf("%05d %d %05d\n", validLink[i].address, validLink[i].data, validLink[i].next);
//     }
//     validLink[i].next = -1;
//     printf("%05d %d -1\n", validLink[i].address, validLink[i].data);
    
// //     for(i=0; i<validNodeCount-1; ++i) // output
// //     {
// //         printf("%05d %d %05d\n", validLink[i].address, validLink[i].data, validLink[i].next);
// //     }
// //     printf("%05d %d -1\n", validLink[i].address, validLink[i].data);
    
    
//     free(linkList);
//     free(validLink);
//     return 0;
// }

// int myCmp(const void *p1, const void *p2)
// {
//     Node *node1 = (Node *)p1;
//     Node *node2 = (Node *)p2;
    
//     if((*node1).class != (*node2).class)
//     {
//         return (*node1).class - (*node2).class;
//     }
//     else // class is equal
//     {
//         return (*node1).order - (*node2).order;
//     }
    
    
// //     if((*node1).class < (*node2).class)
// //     {
// //         return -1;
// //     }
// //     else // class is equal
// //     {
// //         if((*node1).order < (*node2).order)
// //         {
// //             return -1;
// //         }
// //         else
// //         {
// //             return 1;
// //         }
// //     }
    
// //     if((node1->class) < (node2->class))
// //     {
// //         return -1;
// //     }
// //     else // class is equal
// //     {
// //         if((node1->order) < (node2-> order))
// //         {
// //             return -1;
// //         }
// //         else
// //         {
// //             return 1;
// //         }
// //     }
// }

// second way
// #include <stdio.h>
// #include <stdlib.h> // malloc header

// typedef struct node
// {
//     int address;
//     int data;
//     int next;
//     int flag;
// } Node;

// // testpoint5 still time limit exceeded
// int main(void)
// {
//     int pHead=0, nodeCount=0, numK=0;
//     int i=0; //iterator
//     Node *linkList = NULL;
//     Node *validLink = NULL;
//     int validNodeCount = 0;
//     Node *resLink = NULL;
//     int resNodeCount = 0;
    
//     scanf("%d%d%d", &pHead, &nodeCount, &numK);
//     linkList = (Node *)malloc(sizeof(Node) * nodeCount);
//     validLink = (Node *)malloc(sizeof(Node) * nodeCount);
//     resLink = (Node *)malloc(sizeof(Node) * nodeCount);
    
//     for(i=0; i<nodeCount; ++i)
//     {
//         scanf("%d%d%d", &linkList[i].address, &linkList[i].data, &linkList[i].next);
//         linkList[i].flag = 0; // clear flag
        
//         if(linkList[i].address == pHead) // first element
//         {
//             validLink[validNodeCount++] = linkList[i];
//         }
        
//         if(validNodeCount && linkList[i].address == validLink[validNodeCount-1].next) // find next node
//         {
//             validLink[validNodeCount++] = linkList[i];
//         }
//     }
    
//     while(validLink[validNodeCount-1].next != -1) // to find all node on the linkList
//     {
//         for(i=0; i<nodeCount; ++i)
//         {
//             if(validLink[validNodeCount-1].next == -1) break;
            
//             if(linkList[i].address == validLink[validNodeCount-1].next) // find next node
//             {
//                 validLink[validNodeCount++] = linkList[i];
//                 break;
//             }
//         }
//     }
    
//     for(i=0; i<validNodeCount; ++i) // class 1
//     {
//         if(validLink[i].data < 0)
//         {
//             validLink[i].flag = 1; // set flag
//             resLink[resNodeCount++] = validLink[i];
//         }
//     }
    
//     for(i=0; i<validNodeCount; ++i) // class 2
//     {
//         if(!validLink[i].flag && validLink[i].data <= numK)
//         {
//             validLink[i].flag = 1; // set flag
//             resLink[resNodeCount++] = validLink[i];
//         }
//     }
    
//     for(i=0; i<validNodeCount; ++i) // class 3
//     {
//         if(!validLink[i].flag)
//         {
//             resLink[resNodeCount++] = validLink[i];
//         }
//     }
    
    
//     for(i=0; i<validNodeCount-1; ++i) // alter next address and output
//     {
//         resLink[i].next = resLink[i+1].address;
//         printf("%05d %d %05d\n", resLink[i].address, resLink[i].data, resLink[i].next);
//     }
//     resLink[i].next = -1;
//     printf("%05d %d -1\n", resLink[i].address, resLink[i].data);
    
    
//     free(linkList);
//     free(validLink);
//     free(resLink);
//     return 0;
// }


#include <stdio.h>

#define MAX_ADDRESS 100000

typedef struct node
{
    int address;
    int data;
    int next;
    int flag;
} Node;

int main(void)
{
    int pHead=0, nodeCount=0, numK=0;
    int i=0; //iterator
    int resNodeCount = 0;
    Node linkList[MAX_ADDRESS];
    int tempAddress = 0;
    Node resLink[MAX_ADDRESS];
    
    scanf("%d%d%d", &pHead, &nodeCount, &numK);
    
    for(i=0; i<nodeCount; ++i)
    {
        scanf("%d", &tempAddress);
        linkList[tempAddress].address = tempAddress;
        scanf("%d%d", &linkList[tempAddress].data, &linkList[tempAddress].next);
        linkList[tempAddress].flag = 0; // clear flag
    }
    
    tempAddress = pHead;
    while(tempAddress != -1)
    {
        if(linkList[tempAddress].data < 0) // class 1
        {
            linkList[tempAddress].flag = 1; // set flag
            resLink[resNodeCount++] = linkList[tempAddress];
        }
        tempAddress = linkList[tempAddress].next;
    }
    
    tempAddress = pHead;
    while(tempAddress != -1)
    {
        if(!linkList[tempAddress].flag && linkList[tempAddress].data <= numK) // class 2
        {
            linkList[tempAddress].flag = 1; //set flag
            resLink[resNodeCount++] = linkList[tempAddress];
        }
        tempAddress = linkList[tempAddress].next;
    }
    
    tempAddress = pHead;
    while(tempAddress != -1)
    {
        if(!linkList[tempAddress].flag) // class 3
        {
            linkList[tempAddress].flag = 1; // set flag
            resLink[resNodeCount++] = linkList[tempAddress];
        }
        tempAddress = linkList[tempAddress].next;
    }
    
    for(i=0; i<resNodeCount-1; ++i) // alter next address and output
    {
        resLink[i].next = resLink[i+1].address;
        printf("%05d %d %05d\n", resLink[i].address, resLink[i].data, resLink[i].next);
    }
    resLink[i].next = -1;
    printf("%05d %d -1\n", resLink[i].address, resLink[i].data);
    
    
    return 0;
}