第C語言經典順序表真題演練講解目錄1、移除元素2、刪除有序數組中的重復項3、合并兩個有序數組

1、移除元素

鏈接直達：

/problems/remove-element/

題目：

思路：

法一：依次挪動數據進行覆蓋

從第一個數據開始進行依次遍歷，如同示例1，依次遍歷數組，找到移除的元素2就把后面的數據往前挪動進行覆蓋，如圖所示：

此法有個缺陷，題目中明確指出使用空間復雜度O(1)的方法解決此問題，而此法的空間復雜度剛好為O(1)，可以解決，不過考慮周全些，時間復雜度在情況最壞時為O(N^2)，出現全是val的情況，將會挪動n-1+n-2+出現了等差數列，時間復雜度為O(N^2)，此法不是最優，換。

法二：雙指針1.0

依次遍歷原數組，看是不是val，把不是val的值，拷貝到新數組，此法的時間復雜度是O(N)，空間復雜度也是O(N)，可是題目明確指出空間復雜度要為O(1)，所以此法不行，但是仔細想想，如果繼續用此法雙指針，但是不另開數組，就在原數組上改動可否呢？，由此引出雙指針2.0

法三：雙指針2.0

此法是在法二的基礎上進行的升級，法二需要開辟額外數組，此法直接原數組改動。首先定義兩個變量src和dst為0，都作為數組nums的下標，依次遍歷src看nums[src]是否為val，若不是，將其賦給下標dst，再src++，dst++。若nums[src]=nums[dst]，則只把src++，dst不動，最后再把長度dst返回即可。

代碼如下：

intremoveElement(int*nums,intnumsSize,intval){

intdst=0;

intstr=0;

while(strnumsSize)

if(nums[str]==val)

str++;

else

nums[dst]=nums[str];

dst++;

str++;

returndst;

}

2、刪除有序數組中的重復項

鏈接直達：

/problems/remove-duplicates-from-sorted-array/

題目：

思路：

雙指針（不額外開數組）

此題和上題類似，同樣可以采用雙指針，并在原數組進行改動，只需要定義兩個變量dst和src作為數組nums的下標，但此時做出小變動，把src從下標1開始，而dst從下標0開始。讓nums[src]每次和它前一個也就是nums[src-1]相比較，如果相等，則src++，若不等就把nums[src-1]賦給nums[dst]，再dst++，src++。

注意：

執行完上述操作后，還存在一個問題，那就是沒把src的最后一個下標的值放到nums[dst]里頭去，就如同本題的示例，當src走到倒數第二個值3的時候，和前一個3相等，此時需要++src，現在nums[src]就是4，和前一個值不相等，把3賦給nums[dst]，此時src再++到空了，沒有數據和4比較了，越界，所以4就漏掉了。在如同當后面2個數字同為3的時候，因為一直相等，src同樣+到空，3同樣漏掉，所以無論哪種情況，都要把最后一個數字移到nums[dst]上

畫圖演示：

代碼如下：

intremoveDuplicates(int*nums,intnumsSize){

intdst=0;

intsrc=1;

while(srcnumsSize)

if(nums[src]==nums[src-1])

src++;

else

nums[dst]=nums[src-1];

dst++;

src++;

nums[dst]=nums[numsSize-1];

dst++;

returndst;

}

3、合并兩個有序數組

鏈接直達：

合并兩個有序數組

題目：

思路：

法一：memmove+sort排序（冒泡、qsort等）

此法確實可以，不過當題目中明確指出要用時間復雜度O(N)的方法解決此問題的話，那么此法就行不通了，因為冒泡的時間復雜度為O(N^2)，而qsort的時間復雜度為O(N*logN)。均不是O(N)，所以得換。

法二：歸并1.0

依次比較，每次把小的放到歸并數組。此法需要開辟第三方數組a。其次，需要定義i，j，dst三個變量分別用來表示數組nums1，nums2，a的第一個下標，如果nums1[i]nums[j]，則a[dst++]=nums1[i++]，反之a[dst++]=nums2[i++]，依次遍歷下去，當其中一個走完了，就把剩下的全部放到a數組里頭去，此法的最大問題就是需要額外開辟一個數組，以空間換時間，導致空間復雜度為O(N)，但是我們在基于此法的基礎上可以進行升級，如下：

法三：歸并2.0

此法是在法二的基礎上進行升級，直接在nums1原數組上進行改動，思想和法二差不多。不過有個需要改變的地方，法二是正著遍歷數組，但是此法則需要倒著來遍歷數組。那么此時的i變量就是nums1數組第m-1個下標，j變量就是nums2數組第n-1個下標，dst變量就是nums1數組最后一個元素下標（m+n-1）。實現原理同法二，不做過多贅述。注意：如果nums2數組的下標j先結束，那么nums1剩下的數組剛好排在前面，不需要動，如果是nums1數組的下標i先結束，則需要把nums2數組剩余的值賦到nums1數組上去。

畫圖演示：

代碼如下：

voidmerge(int*nums1,intnums1Size,intm,int*nums2,intnums2Size,intn){

inti=m-1;

intj=n-1;

intdst=m+n-1;

while(i=0j=