1、移除元素

鏈接直達：

https://leetcode-cn.com/problems/remove-element/

題目：

思路：

法一：依次挪動數(shù)據(jù)進行覆蓋

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

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

法二：雙指針1.0

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

法三：雙指針2.0

此法是在法二的基礎(chǔ)上進行的升級，法二需要開辟額外數(shù)組，此法直接原數(shù)組改動。首先定義兩個變量src和dst為0，都作為數(shù)組nums的下標(biāo)，依次遍歷src看nums[src]是否為val，若不是，將其賦給下標(biāo)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、刪除有序數(shù)組中的重復(fù)項

鏈接直達：

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/

題目：

思路：

雙指針（不額外開數(shù)組）

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

注意：

執(zhí)行完上述操作后，還存在一個問題，那就是沒把src的最后一個下標(biāo)的值放到nums[dst]里頭去，就如同本題的示例，當(dāng)src走到倒數(shù)第二個值3的時候，和前一個3相等，此時需要++src，現(xiàn)在nums[src]就是4，和前一個值不相等，把3賦給nums[dst]，此時src再++到空了，沒有數(shù)據(jù)和4比較了，越界，所以4就漏掉了。在如同當(dāng)后面2個數(shù)字同為3的時候，因為一直相等，src同樣+到空，3同樣漏掉，所以無論哪種情況，都要把最后一個數(shù)字移到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、合并兩個有序數(shù)組

鏈接直達：

合并兩個有序數(shù)組

題目：

思路：

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

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

法二：歸并1.0

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

法三：歸并2.0

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

畫圖演示：

 代碼如下：

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--];
    }
}

到此這篇關(guān)于C語言經(jīng)典順序表真題演練講解的文章就介紹到這了,更多相關(guān)C語言 順序表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論