題目內容：
給你一個陣列 nums 和一個值 val，你需要 原地 移除所有數值等于 val 的元素，并回傳移除后陣列的新長度，
不要使用額外的陣列空間，你必須僅使用 O(1) 額外空間并原地修改輸入陣列，
元素的順序可以改變，你不需要考慮陣列中超出新長度后面的元素，
leetcode題目鏈接（點擊即可跳轉）：
思路分析
①看完了題目，我們首先來理解一下題目的含義，
這個題目其實就算是說，有一個陣列，而且還是一個整型陣列，陣列里面有一堆數字，然后給你一個特定的數字，這個數字有可能在陣列里面找不到，也有可能找得到，如果能找到，就需要將陣列里面中和這個數字相同的元素全部洗掉掉，最后得到一個新的陣列，
題目里面說了“原地”，可能我們暫時并不理解“原地”是什么意思，我們可以先不管，為了解決上面說的“洗掉陣列所有特定值”的這個問題，可以采取哪些方法呢？（先思考一下再進行往下看哦！）
是的，我們可以先創建一個臨時陣列，大小可以和原陣列大小一樣，然后將原陣列中不為特定值的元素（也就是 值 ≠ val）挪到臨時陣列中，跳過是特定值的元素（值 = val），最后將臨時陣列中的元素拷貝回原陣列，即可解決這個問題，圖解如下：
這種方法相信大部分同學都可以想到，但是這個方法有一個很明顯的缺陷—當原陣列很大的時候，比如說原陣列有10萬個資料，那么就需要開辟一個可以存10萬個資料的臨時陣列，并且這個臨時陣列的大小還需要根據原陣列的大小不停的變動，在實際中，這種方法很不實用（呆呆的，就是有點呆），
那么能不能不需要創建臨時陣列就解決這個問題呢？
（額，既然我都問了，那肯定是有的）
方法一：元素覆寫法（有坑！）
我們可以借鑒順序表的頭刪（或者中間任意位置洗掉）的操作—用后面的元素覆寫前面的元素實作資料的洗掉，
相關文章：
【資料結構學習筆記】二、線性表—順序表篇（1）（畫圖詳解+代碼實作）
函式介面實作：
int removeElement(int* nums, int numsSize, int val){
//首先判斷陣列是否為空
if(numsSize == 0)
return 0;
int i = 0;//用來遍歷陣列元素
int end = numsSize - 1;//用來記錄最后一個元素的下標
while(i <= end){
//注意對最后一個元素的處理
if(nums[i] == val){
//從前往后依次覆寫
for(int j = i;j < end; j++){
nums[j]=nums[j+1];
}
//覆寫后陣列長度-1
end--;
}
}
//此時新陣列的長度是end+1
return end+1;
}
當我們寫完這段代碼的時候，可能會欣喜若狂，實際上去測驗的時候，卻會嚎啕大哭，因為這段代碼可能連測驗案例都通過不了QAQ，Orz（跪了！）納尼，怎么回事？？小朋友，是不是有很多問號？？？
測驗案例通過不了的原因是“超出時間限制”，也就是耗時太多了，時間復雜度沒有達到要求，假設問題規模為n（也就是原陣列的長度為n），那么上面這段代碼的時間復雜度為O(n^2)（n的平方的效率），
時間復雜度、空間復雜度相關文章：
【資料結構學習筆記】一、資料結構介紹及演算法分析（新手入門進階指南）
然后我又悄悄回到 leetcode做題頁面，重新審題，看有沒有時間復雜度的限制要求，結果發現題目本身并沒有對時間復雜度有任何要求，只要求了空間復雜度為O（1）（也就是原地起飛），，，（坑爹啊！）
方法二：虛擬陣列法（正確的方法）
既然元素覆寫的方法在 leetcode無法通過測驗（雖然這種方法本身沒有任何問題，自己在VS中寫的測驗用例也能通過），作為一名合格的編程學習者，自然要尋找另外一種更高效的方法，我們一開始談到了臨時陣列法來處理這個問題，但是因為不滿足空間復雜度O（1）的要求，所以沒有采納這種方法，但實際上這種方法的基本思想是正確的，將值非val的元素保留到陣列中，值為val的元素丟棄掉，根據這種思想，我們可以想出虛擬陣列的方式，也就是假設有一個臨時陣列，但是這個臨時陣列又不需要我們真正去開辟出來，而是借用原來的陣列本身來實作臨時陣列的功能！（Nb，666，厲害了！！！）
演算法圖解：
函式介面實作：
int removeElement(int* nums, int numsSize, int val){
//首先判斷陣列長度是否為0
if(numsSize == 0)
return 0;
int src = 0;
int dest = 0;
while(src < numsSize){
if(nums[src] != val){
nums[dest++] = nums[src++];//保留給dest的同時，同時向后移動
}
else{
src++;
}
}
return dest;//此時陣列的長度就是dest,dest是指向下個元素的下標
}
倒騰了半天，終于成功的解決了這個問題，趕緊打開音樂播放器，播放“開心的鑼鼓敲出年年的喜慶~ …今天是個好日子，心想的事情都能成~”
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/398689.html
標籤：其他