时间复杂度与空间复杂度题目讲解

前言：

在前面我们了解到了时间复杂度与空间复杂度，这里我们就可以尝试一下做一些关于时间复杂度与空间复杂度的题目。

1. 数组篇

题目一：消失的数字

消失的数字：. - 力扣（LeetCode）

思路：

看到这个题目，我们首先的思路是先排序，然后如果后一个数字不等于前一个数字+1的话，那么这个就是消失的数字，那么排序，我们选择冒泡排序呢还是qsort排序，我们发现这个题目限制了时间复杂度为0(N),冒泡排序的时间复杂度是O(N^2),这个不行，那么我们选择qsort排序吗？qsort排序的时间复杂度是O(N*logn)，这个貌似也是不行的。

这里我们就需要利用到一种新的思路了，用异或^来进行解决，我们知道0^任何数都是任何数，相同的数异或就是0,比如说1^2^1的结果是2，我们利用这个思路，首先用0来异或0到N之间的所有数字，然后再把这个结果拿到数组里面进行异或，最后异或的结果就是那个消失的数字。

时间复杂度是O(N)

空间复杂度是O(1)

代码：

int missingNumber(int* nums, int numsSize){
    int ret = 0;
    //这里我们先异或0到N之间的数字
    for(int i = 0;i<=numsSize;i++)
    {
        ret = ret^i;
    }
    //然后将异或完的结果拿到数组里面进行异或
    for(int i = 0;i < numsSize; i++)
    {
        ret= ret^nums[i];
    }
    //最后的结果就是消失的数字，我们直接返回这个值
    return ret;
}

题目二：轮转数组

轮转数组：. - 力扣（LeetCode）

思路：

首先看到这个题目，我们的想法是，先创建一个变量把数组的最后一个元素存起来，然后将数组整体完后移动一位，然后将存起来的元素放在数组的首元素，然后循环k次，这样就完成了，但是这个思路过不了这个题目。

这里力扣给出了一个超长的数组。所以过不了。

那我们就选择另一种思路：

三段逆置法

我们首先将数组的前numsSize-k个数据进行逆置，然后再将数组的后k个数据进行逆置，最后将我们的数组整体进行逆置，这样就完成了轮转数组。

时间复杂度为O(N)

空间复杂度为O(1)

当然，这一种思路可能不是那么容易想到

我们这里还有一种思路，创建一个数组，然后将原数组的后k个拷贝到新数组里面，然后再将前numsSize-k个拷贝到新数组里面，最后再将新数组里面的数据都拷贝到原数组里面，这样

也可完成这个轮转数组

时间复杂度为O(N)

空间复杂度为O(N)

三段逆置代码：

void revolve(int*a ,int m,int n)
{
   int left = m;
   int right = n;
   while(left < right)
   {
     int tmp = a[left];
     a[left] = a[right];
     a[right] = tmp;
     left++;
     right--;
   }
}
void rotate(int* nums, int numsSize, int k) {
    k = k % numsSize;
    //将数组的前numsSize-k个逆置
    revolve(nums,0,numsSize-k-1);
    //将数组的后k个逆置
    revolve(nums,numsSize-k,numsSize-1);
    //将数组整体逆置
    revolve(nums,0,numsSize-1);
}

创建新数组拷贝方法：

void _rotate(int*nums,int numsSize,int k,int*tmp)
{
    k = k%numsSize;
    int n = numsSize;
    //将后k个数据拷贝到新数组里面
    memcpy(tmp,nums+n-k,sizeof(int)*k);
    //将前n-k个数据拷贝到新数组里面
    memcpy(tmp+k,nums,sizeof(int)*(n-k));
    //将新数组里面的数据全部拷贝到原数组里面
    memcpy(nums,tmp,sizeof(int)*n);
}
void rotate(int* nums, int numsSize, int k) {
    int tmp[numsSize];
    _rotate(nums,numsSize,k,tmp);
     
}

2. 单链表篇

题目一：返回倒数第k个节点

返回倒数第k个节点：. - 力扣（LeetCode）

这里如果说给我们加上一个限制条件，空间复杂度是O(1),只能遍历一遍链表，那么这个题应该怎么解呢

思路：

首先，我们用到我们之前使用过的快慢指针这样的一个解法，我们先让快指针走k步，然后它们两个同时走，当快指针走到空时，慢指针刚好走到倒数第k个节点。

时间复杂度为O(N)

空间复杂度为O(1)

代码：

typedef struct ListNode sl;
int kthToLast(struct ListNode* head, int k){
    //首先我们创建两个指针
    sl* slow = head;
    sl* fast = head;
    //让快指针先走k步
    while(k--)
    {
        fast = fast->next;
    }
    //再两个指针同时走
    while(fast)
    {
        fast = fast->next;
        slow = slow->next;
    }
    //当快指针走到空时，这时慢指针刚好就是倒数第k个节点
    return slow->val;
}

题目二：回文链表

回文链表：. - 力扣（LeetCode）

这里可能很多人不清楚，什么是回文，回文相当于是链表从中间切开是对称的。

思路：

我们这里首先要找到链表的中间节点，然后将中间节点之后的节点进行逆置，我们再从链表的第一个有效节点和链表的中间节点开始进行比对。

代码：

typedef struct ListNode sl;

 sl* revse(sl* phead)
 {
    sl* p1 = NULL;
    sl* p2 = phead;
    sl* p3 = phead->next;
    while(p2)
    {
        p2->next = p1;
        p1 = p2;
        p2 = p3;
        if(p3!= NULL)
        {
            p3 = p3->next;
        }
    }
    return p1;
 }
bool isPalindrome(struct ListNode* head) {
    //创建快慢指针，找中间节点
    sl* slow = head;
    sl* fast = head;
    while(fast&&fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    //将中间节点之后的节点逆置
    sl* phead  = revse(slow);
    sl* pcur = head;
    //遍历链表进行比对
    while(phead)
    {
        if(phead->val!= pcur->val)
        {
            return false;
        }
        pcur = pcur->next;
        phead = phead->next;
    }
    return true;
}

题目三：相交链表

相交链表:. - 力扣（LeetCode）

思路：

要解决这一题，首先我们要判断链表是否相交。怎么判断相交呢？我们直接看两个链表的尾节点的地址是否相同，如果相同，就是相交的，反之就是不相交，这里我们判断尾节点是否相同的时候，不要用节点里面的数据来判断是否相交，这样容易出错。

到这里，就说明它们两个相交了，那么这里我们有两种思路可以求解

思路1：暴力求解，将A链表的节点依次的跟B链表的所有节点进行比较，A链表某个节点跟B链表的某个节点相同，这个节点就是交点。我们考虑这个思路的时候也是可以分析一下它的时间复杂度，这个链表肯定需要两层循环来帮助我们进行判断，那么它的时间复杂度为O(N^2)。

思路2：若不想采取思路1的方法，我们是否可以找到更优的解法呢?当然有，就是让两个链表从同一个位置开始走，怎么样才能让两个链表从同一个位置走呢？我们先计算A链表的长度，在计算B链表的长度，算出它们长度的差，让开链表先走差距步，然后再让两个链表同时走，找相同节点的地址，这个节点就是它们的交点。我们简单分析一下，这个思路的时间复杂度为O(N)，发现比前一个思路更优，那我们就采取第二种方法进行求解。

代码：

typedef struct ListNode sl;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    //创建两个指针遍历两个链表
    sl* pcura = headA;
    sl* pcurb = headB;
    //创建两个变量记录两个链表的长度
    int counta = 0;
    int countb  = 0;
    while(pcura->next)
    {
        pcura = pcura->next;
        ++counta;
    }
    while(pcurb->next)
    {
        pcurb = pcurb->next;
        ++countb;
    }
    //判断两个尾节点是否相同
    if(pcura != pcurb)
    {
        return NULL;
    }
    //这里计算出它们两个的差距
    int gap = abs(counta-countb);
    //我这里先使用假设法，假设长链表是A链表，短链表是B链表
    sl* longlist = headA;
    sl* shortlist = headB;
    //这里再判断B链表节点的个数大于A链表节点，再设置谁是长链表，谁是短链表
    if(countb>counta)
    {
      longlist = headB;
      shortlist = headA;
    }
    //让长链表先走差距步
    while(gap--)
    {
        longlist = longlist->next;
    }
    //再两个链表同时走
    while(longlist!=shortlist)
    {
        longlist = longlist->next;
        shortlist = shortlist->next;
    }
    //最后随便返回两个链表中的一个节点地址就好了
    return shortlist;
    
}

题目四：环形链表Ⅰ

环形链表Ⅰ：. - 力扣（LeetCode）

思路：

这里我们采用快慢指针的思路来进行解题，这里我们让慢指针一次走一步，快指针一次走两步，这样就变成了一个追击问题了，如果快指针在环里面碰见了慢指针，说明带环，如果快指针走到了空，说明是不带环的。

代码：

typedef struct ListNode sl;
bool hasCycle(struct ListNode *head) {
    //创建快慢指针
    sl* slow = head;
    sl* fast = head;
    //循环遍历链表
    while(fast&&fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        //如果快指针在环里面遇见了慢指针
        if(fast == slow)
        {
            //说明带环
            return true;
        }
    }
    //如果出了循环，代表链表不带环
    return false;
}

其实呢？这个题目的考点是这样的。

1.为什么一定会相遇，有没有可能会错过，永远追不上？请你证明

2.slow每次走1步，fast每次走3步，4步，5步，N步，请证明一定会追上吗？

这里我们就简单用fast每次走三步来进行证明：

这里永远追不上的条件有两个

1.N是奇数 2.c-1是奇数

那么，存在同时N是奇数且C是偶数的情况吗？

其实不会同时存在这两种情况，所以一定能追上。

其他fast走4步，5步,N步推理同理，只不过情况不一样。

题目五：环形链表Ⅱ

环形链表Ⅱ：. - 力扣（LeetCode）

思路：

这个题目需要我们判断链表是否带环，如果带环，找出入环的第一个节点。

思路1：这里我们找到它们的相遇点，然后然后创建一个指针newhead指向相遇点的下一个节点，再将相遇点的指针指向置为空，然后再定义一个指针指向原链表的头，这样就变成两个链表的相交问题了

思路2：直接使用双指针法，一个从头节点开始走，一个从相遇点开始走，当这两个指针再次相遇的地方就是链表入环的第一个节点。

这里我们采取的是思路二的代码

代码：

typedef struct ListNode sl;
struct ListNode *detectCycle(struct ListNode *head)
 {
    //创建快慢指针
    sl* slow = head;
    sl* fast = head;
    while(fast&&fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        //如果带环
        if(fast == slow)
        {
            //创建指针指向相遇的节点
              sl* meet = fast;
              //慢指针从头开始走
              slow = head;
              //遍历链表
              while(slow)
              {
                //如果相遇了
                if(meet == slow)
                   {
                    //说明这个节点就是入环口
                       return meet;
                   }
             meet = meet->next;
             slow = slow->next;
             }
        }
    }
    return NULL;
}

这里有一个问题，为什么从meet节点走和从头节点开始走时的路程是一样的。

题目六：随机链表的复制

随机链表的复制:. - 力扣（LeetCode）

什么是深拷贝？

深拷贝：拷贝一个值和指针指向跟当前链表一模一样的链表

思路：

这个题目拷贝链表不是问题，问题在于怎么把拷贝链表的random指针的指向弄准确，这里就有一个方法，我们把每个拷贝的节点都插入在链表节点的后面，那么拷贝节点就跟链表节点有了关联，再将拷贝节点的random指针指向对应的拷贝节点，最后再将拷贝节点从原链表上面拿下来。这样就完成了复杂链表的拷贝。

代码：

typedef struct Node sl;
struct Node* copyRandomList(struct Node* head) {
  sl* pcur = head;
  //将拷贝的每一个节点都尾插在原链表节点的后面
  while(pcur)
  {
     sl* copy = (sl*)malloc(sizeof(sl));
     copy->val = pcur->val;
     copy->next = pcur->next;
     pcur->next = copy;
     pcur = copy->next;
  }
  pcur = head;
  //将拷贝的每个节点的random指向对应的拷贝节点
  while(pcur)
  {
    sl* copy = pcur->next;
    if(pcur->random == NULL)
    {
        copy->random = NULL;
    }
    else
    {
        copy->random = pcur->random->next;
    }
    pcur = copy->next;
  }
  //创建新链表进行接收拷贝的所有节点
  pcur = head;
  sl*phead = NULL;
  sl* ptail = NULL;
  while(pcur)
  {
    sl* copy = pcur->next;
    sl*next = copy->next;
    if(phead == NULL)
    {
        phead= ptail = copy;
    }
    else{
        ptail->next = copy;
        ptail = ptail->next;
    }
    pcur = next;
  }
  return phead;
}