前言?

📚作者簡介：愛編程的小馬，正在學習C/C++，Linux及MySQL。

📚本文收錄與初階數據結構系列，本專欄主要是針對時間、空間復雜度，順序表和鏈表、棧和隊列、二叉樹以及各類排序算法，持續更新！

📚相關專欄C++及Linux正在發展，敬請期待！

1.1 第一題?

首先說明需要使用leetcode力扣這個平臺進行算法的練習，第一道題的OJ鏈接我放在這里，同學們點進去就可以做題了：移除元素

題目描述：

給你一個數組?nums?和一個值?val，你需要原地移除所有數值等于?val?的元素，并返回移除后數組的新長度。

不要使用額外的數組空間，你必須僅使用?O(1)?額外空間并原地修改輸入數組。

題目分析：?

這道題實際上考查的是不開辟新的數組空間，能不能在原數據上操作就可以完成刪除。

我給同學們提供一個思路，供你們參考

??

?首先建立兩個指針，都指向數據的首元素的位置，然后src依次往后走，?如果和val相同我就跳過，如果不同我就把這個位置的元素拷貝到dst指向的位置，然后dst往后走，src往后走，遍歷完成了，是不是返回dst就可以了，我們一起來實現一下這個代碼：??

int removeElement(int* nums, int numsSize, int val)
{int src = 0;int dst = 0;while(src<numsSize){if(nums[src] == val){src++;}else{nums[dst++] = nums[src++];}}return dst;
}

?1.2 第二題?

第二題的OJ鏈接：刪除有序數組中的重復項?

?題目描述：

給你一個非嚴格遞增排列的數組?nums?，請你原地刪除重復出現的元素，使每個元素只出現一次?，返回刪除后數組的新長度。元素的?相對順序?應該保持?一致?。然后返回?nums?中唯一元素的個數。

• 更改數組?nums?，使?nums?的前?k?個元素包含唯一元素，并按照它們最初在?nums?中出現的順序排列。nums?的其余元素與?nums?的大小不重要。
• 返回?k?。

?題目思路：

這道題雖然提示了說需要原地刪除，但是沒有限定完全空間復雜度，所以使用新數組也能過，但是我在這里給大家講解一種新的方法，原地刪除。

??

就是src1 和 src2用于遍歷數組，當src1和src2的數據元素值不同時，就把src1的值拷貝給dst，然后dst往后走一步，這時候再把src2拷貝給src1繼續遍歷是不是就完成了？一起來看下代碼：?

int removeDuplicates(int* nums, int numsSize) 
{int src1 = 0;int src2 = 1;int dst = 0;while(src2<numsSize){if(nums[src2] != nums[src1]){nums[++dst] = nums[src2];src1 = src2;}else{src2++;}}return dst+1;
}

?1.3 第三題?

?第三題的OJ鏈接：合并兩個有序數組

給你兩個按非遞減順序排列的整數數組?nums1?和?nums2，另有兩個整數?m?和?n?，分別表示?nums1?和?nums2?中的元素數目。

請你合并?nums2?到?nums1?中，使合并后的數組同樣按非遞減順序排列。

注意：最終，合并后數組不應由函數返回，而是存儲在數組?nums1?中。為了應對這種情況，nums1?的初始長度為?m + n，其中前?m?個元素表示應合并的元素，后?n?個元素為?0?，應忽略。nums2?的長度為?n?。

題目分析：?

這道題也是希望不開辟新數組，就在原數組中完成合并。很多同學就說了，是不是我可以先把兩個數組合并，再用快排qsort排序就可以了？其實不行，為什么呢？qsort的時間復雜度是O(N)=N*logN，在OJ題肯定過不去，那我們有沒有辦法在O(N)的時間復雜度下完成這個算法呢？

??

?這樣子可不可以，其實不行。同學們想一想，如果我按照題意如果我再nums1，可能是從后往前插入，如果從前往后是會造成數據的覆蓋的，那么我們是不是從后往前遍歷，依次比較是不是就可以。??

??

然后還有一個點，就是如果nums2先結束，那沒問題，輸入nums1即可，但是nums1先結束呢？是不是還需要把nums2之后的值拷貝到nums1中，結束為止，在輸出nums1，對不對，這樣是不是就可以了？同學們一起看下代碼：?

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{int end1 = m-1;int end2 = n-1;int i = m+n-1;while(end1>=0 && end2 >=0){if(nums1[end1]>nums2[end2]){nums1[i--] = nums1[end1--];}else{nums1[i--] = nums2[end2--];}}while( end2 >= 0 ){nums1[i--] = nums2[end2--];}
}

1.4 第四題?

第四題的OJ鏈接：?消失的數字

題目描述：數組nums包含從0到n的所有整數，但其中缺了一個。請編寫代碼找出那個缺失的整數。你有辦法在O(n)時間內完成嗎？

題目分析：

這道題可以用暴力解決的，就是我把新數組和i依次遍歷比較，找出那個不相等的，然后返回就可以了，這個的時間復雜度是多少，其實是O(N) = N^2，肯定是過不去的。

那我們可以使用一個很巧的方法，是異或法，怎么操作呢?因為異或有個很好的特性是相同為0，所以分別異或兩次是不是就可以找到了？比方說看我這個圖：

??

代碼：

int missingNumber(int* nums, int numsSize)
{int ret = 0;for(int i = 0; i<numsSize;i++){ret ^= nums[i]; }for(int i = 0; i<numsSize+1;i++){ret ^= i; }return ret;
}

總結

1、同學們一定要將這次講的題都自己做一遍，對順序表會有更好的理解

2、算法題和我們之前刷的牛客網題還不一樣，大家一開始要適應

如果這份博客對大家有幫助，希望各位給小馬一個大大的點贊鼓勵一下，如果喜歡，請收藏一下，謝謝大家！！！
制作不易，如果大家有什么疑問或給小馬的意見，歡迎評論區留言。