C語言經典順序表實例分析

這篇“C語言經典順序表實例分析”文章的知識點大部分人都不太理解，所以小編給大家總結了以下內容，內容詳細，步驟清晰，具有一定的借鑒價值，希望大家閱讀完這篇文章能有所收獲，下面我們一起來看看這篇“C語言經典順序表實例分析”文章吧。

1、移除元素

題目：

思路：

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

從第一個數據開始進行依次遍歷，如同示例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、刪除有序數組中的重復項

題目：

思路：

雙指針（不額外開數組）

此題和上題類似，同樣可以采用雙指針，并在原數組進行改動，只需要定義兩個變量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語言經典順序表實例分析”這篇文章的內容，相信大家都有了一定的了解，希望小編分享的內容對大家有幫助，若想了解更多相關的知識內容，請關注億速云行業資訊頻道。