1、移除元素

鏈接直達(dá)：

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

題目：

思路：

法一：依次挪動(dòng)數(shù)據(jù)進(jìn)行覆蓋

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

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

法二：雙指針1.0

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

法三：雙指針2.0

此法是在法二的基礎(chǔ)上進(jìn)行的升級，法二需要開辟額外數(shù)組，此法直接原數(shù)組改動(dòng)。首先定義兩個(gè)變量src和dst為0，都作為數(shù)組nums的下標(biāo)，依次遍歷src看nums[src]是否為val，若不是，將其賦給下標(biāo)dst，再src++，dst++。若nums[src]=nums[dst]，則只把src++，dst不動(dòng)，最后再把長度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ù)項(xiàng)

鏈接直達(dá)：

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

題目：

思路：

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

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

注意：

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

鏈接直達(dá)：

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

題目：

思路：

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

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

法二：歸并1.0

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

法三：歸并2.0

此法是在法二的基礎(chǔ)上進(jìn)行升級，直接在nums1原數(shù)組上進(jìn)行改動(dòng)，思想和法二差不多。不過有個(gè)需要改變的地方，法二是正著遍歷數(shù)組，但是此法則需要倒著來遍歷數(shù)組。那么此時(shí)的 i 變量就是nums1數(shù)組第m-1個(gè)下標(biāo)，j變量就是nums2數(shù)組第n-1個(gè)下標(biāo)，dst變量就是nums1數(shù)組最后一個(gè)元素下標(biāo)（m+n-1）。實(shí)現(xiàn)原理同法二，不做過多贅述。注意：如果nums2數(shù)組的下標(biāo) j 先結(jié)束，那么nums1剩下的數(shù)組剛好排在前面，不需要?jiǎng)樱绻莕ums1數(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--];
    }
}