C語言經典順序表真題演練講解

1、移除元素

連結直達：

https://leetcode-cn.com/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返回即可。

程式碼如下：

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

2、刪除有序陣列中的重複項

連結直達：

https://leetcode-cn.com/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]上

畫圖演示：

程式碼如下：

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

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陣列上去。

畫圖演示：

 程式碼如下：

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

到此這篇關於C語言經典順序表真題演練講解的文章就介紹到這了,更多相關C語言 順序表內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！