O(n)时间复杂度还是TLE,为什么???
查看原帖
O(n)时间复杂度还是TLE,为什么???
706459
Go_for_itligli666666楼主2022/7/19 16:43

TLE了 3 4 5点

#include<iostream>
using namespace std;
struct Node{
    long num;
    Node* next;
    Node(long _num=0,Node*_next=nullptr):num(_num),next(_next){}
};

int main(){
    long N;
    //cin>>N;
    scanf("%ld",&N);
    Node*head=new Node(1);
    //cout<<head->num<<endl;
    for(long i=2;i<=N;i++){
        long k,p;
        //cin>>k>>p;
        scanf("%ld %ld",&k,&p);
        if(p==1){
            //i放在k右边
            Node*temp=head;
            while(temp){
                if(temp->num==k){
                    break;
                }
                temp=temp->next;
            }
            Node*temp2=temp->next;
            temp->next=new Node(i,temp2);
        }
        else{
            //i放在k左边
            Node*fast=head;
            if(fast->num==k){
                head=new Node(i,head);
                continue;
            }
            else{
                while(fast->next){
                    if(fast->next->num==k){
                        break;
                    }
                    fast=fast->next;
                }
                Node*slow=fast->next;
                fast->next=new Node(i,slow);
            }
        }
    }
    
/*    cout<<"**************删除前检验**************"<<endl;
    Node*p=head;
    while(p){
        cout<<p->num<<" ";
        p=p->next;
    }
    cout<<endl;
*/   
    long M;
    //cin>>M;//要删除的同学
    scanf("%ld",&M);
    for(long i=0;i<M;i++){
        long x;
        //cin>>x;
        scanf("%ld",&x);
        //删除编号为x的同学
        if(head->num==x){
            Node*temp=head;
            head=head->next;
            delete temp;
        }
        else{
            Node*fast=head;
            while(fast->next){
                if(fast->next->num==x){
                    break;
                }
                fast=fast->next;
            }
            if(fast->next==nullptr){
                continue;
            }
            Node*temp=fast->next->next;
            delete fast->next;
            fast->next=temp;
        }
    }
    
    //输出结果
    //cout<<"*******结果*******"<<endl;
    Node*temp=head;
    while(temp){
        printf("%ld ",temp->num);
        temp=temp->next;
    }
    
    //delete,释放内存
    while(head){
        Node*temp=head;
        head=head->next;
        delete temp;
    }
    return 0;
}
2022/7/19 16:43
加载中...