关于#c++#的问题：求解一下这个ci zhe ge k f

Question

求解一下这个ci zhe ge k f和d办法课程哦从这里开始看大家反馈日常n热闹

Answer 1

双循环遍历时间复杂度是O(N²)。
可以先排序——用归并排序时间复杂度是O(Nlog(N))——再剔除，因为排序后相同的都相邻，一次循环就可以全部剔除，所以剔除的时间复杂度是O(N)。于是总体时间复杂度为O(Nlog(N))。

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

typedef struct student_test {
    int val;
    struct student_test*next;
} node;

//类似于strcmp 
int cmp_test(node*a, node*b) { 
    return a->val - b->val;
}

node* next_n(node*p, int n) {
    while (p && n--) { 
        p = p->next;
    }
    return p;
}
//两个有序链表合并
void lmerge(node **h, node **t, node *h1, node *e1, node *h2, node *e2, int (*cmp)(node*, node*)) {
    node h3, *p, *q;
    *t = &h3;
    for (p = h1, q = h2; p != e1 && q != e2;) {
        if (cmp(p, q)<=0) {
            (*t)->next = p, *t = p, p = p->next;
        } else {
            (*t)->next = q, *t = q, q = q->next;
        }
    }
    while (p != e1) (*t)->next = p, *t = p, p = p->next;
    while (q != e2) (*t)->next = q, *t = q, q = q->next;
    (*t)->next = NULL;
    (*h) = h3.next;
}

//链表归并排序，时间复杂度为O(nlog(n))，空间复杂度为O(1) 
void lsort(node **head, int (*cmp)(node*, node*)) {
    node *t, *l, *m, *r, hh;
    int w;
    for (w = 1; next_n(*head, w); w <<= 1) {
        t = &hh;
        for (l = *head; l; l = r) {
            m = next_n(l, w);
            r = next_n(m, w);
            if (!m) 
                while (l)t->next = l, t = l, l = l->next;
            else
                lmerge(&t->next, &t, l, m, m, r, cmp);
        }
        *head = hh.next;
        //t->next = NULL;
    }
}

int main() {
    node head={0,NULL},*p,*q;
    int n,i,count=0;
    scanf("%d",&n);
    p=&head;
    for(i=0;i<n;i++){
        p->next=(node*)malloc(sizeof(node));
        p=p->next;
        scanf("%d",&p->val);
    }
    p->next=NULL;
    lsort(&head.next,cmp_test);
    printf("被删除的元素：");
    for(p=head.next;p!=NULL;p=q){//看起来像双循环，实际上只遍历了一次 
        for(q=p->next;q!=NULL && p->val==q->val;q=p->next){
            printf("%d ",q->val);
            p->next=q->next;
            free(q);
            count++;
        }
    }
    printf("\n删除个数：%d",count);
    for(p=head.next;p!=NULL;){
        q=p->next;
        free(p);
        p=q;
    }
    return 0;
}