問(wèn)題描述

原題鏈接：https://leetcode.cn/problems/remove-element/

解題方案

思路一

思路一：

首先通過(guò)簡(jiǎn)單分析，很明顯這是一道順序表相關(guān)問(wèn)題。首先能夠想到的是暴力求解，即思路一：找到所有的val，每次挪動(dòng)val后的數(shù)據(jù)覆蓋刪除val。

??代碼展示：

int find(int*nums,int numsSize,int val)
{
     int i=0;
    for(i=0;i<numsSize;i++)
    {
        if(nums[i]==val)
            return i;
    }
    return -1;
}
int removeElement(int* nums, int numsSize, int val)
{
   int ret;
    while((ret=find(nums,numsSize,val))!=-1)
    {
        for(int i=ret;i<numsSize-1;i++)
        {
            nums[i]=nums[i+1];
        }
        numsSize--;
    }
   return numsSize;
}

但是對(duì)于思路一，空間復(fù)雜度顯然是O(1)，當(dāng)我們計(jì)算時(shí)間復(fù)雜度的時(shí)候，最壞的情況是數(shù)組中大部分值都為val，這時(shí)時(shí)間復(fù)雜度近似為O(1+2+……+n-1)即O(n^2)，顯然O(n^2)的時(shí)間復(fù)雜度還是不盡人意，本著降低時(shí)間復(fù)雜度，我們可以怎樣優(yōu)化呢？

思路二

思路二：

在創(chuàng)建一個(gè)臨時(shí)數(shù)組tmp，遍歷nums數(shù)組，把不是val的數(shù)值放到tmp數(shù)組，最后把tmp數(shù)組的內(nèi)容依次拷貝到nums數(shù)組，返回tmp數(shù)組長(zhǎng)度。

??代碼展示：

int removeElement(int* nums, int numsSize, int val)
{
    if(numsSize==0)//特殊處理
        return 0;
    int i=0;
    int tmp[numsSize];
    int count=0;
    for(i=0;i<numsSize;i++)
    {
        if(nums[i]!=val)
        {
            tmp[count]=nums[i];
            count++;
        }
    }
    for(i=0;i<numsSize;i++)
    {
        nums[i]=tmp[i];
    }
    return count;
}

注釋?zhuān)哼@里的特殊處理是因?yàn)樵诤瘮?shù)中使用了變長(zhǎng)數(shù)組 int tmp[numsSize];而變長(zhǎng)數(shù)組的大小不能為0，這是使用特殊處理，是因?yàn)榱鄣臏y(cè)試用例中含有[] 0。

對(duì)于思路二，最壞的情況我們只遍歷了1遍數(shù)組，即時(shí)間復(fù)雜度為O(n)，但是這明顯是一種用空間換區(qū)時(shí)間的方法，在此過(guò)程我們創(chuàng)建了numsSize個(gè)變量，即空間復(fù)雜度為O(n)。所以我們能不能通過(guò)再降低空間復(fù)雜度，進(jìn)一步優(yōu)化呢？

思路三(最優(yōu)解)

思路三：

創(chuàng)建兩個(gè)變量src、dest，初始時(shí)指向首部，判斷nums[src]是否等于val，如果等于val則dest指向不動(dòng)，src向后偏移，直到nums[src]!=val，令nums[dest]=nums[src]，然后src、dest都向后偏移，直到src遍歷完數(shù)組，程序結(jié)束。

??代碼展示：

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

這種思路下時(shí)間復(fù)雜度為遍歷整個(gè)數(shù)組O(n)，創(chuàng)建的變量為有限個(gè)，所以空間復(fù)雜度為O(1)。相比之下為最優(yōu)解。