解題思路:
? ? ? ? 1.獲取信息:
? ? ? ? ? ? ? ? 給定一個數組和一個值,刪除數組中等于這個值的值
? ? ? ? ? ? ? ? 要求是,返回數組中不等于這個值的數的數目
? ? ? ? ? ? ? ? 并且要求在數組上刪除,不能使用額外輔助空間
? ? ? ? ? ? ? ? 還是給了評測標準(你可以根據它的原理來實現越獄,但不建議,還是老老實實地才能磨練自己哦)我們知道,它是根據你返回的數組中不等于那個值的數的數目來進行查驗進行刪除后的數組的前幾個元素是否與正確答案一致來進行判別的
? ? ? ? ? ? ? ? 所以,數組的大小和除數組前幾個元素外的其他元素并不重要
? ? ? ? 2.分析題目:
? ? ? ? ? ? ? ? 26題是刪除數組中重復的項,與這道題類似,那我們可以嘗試使用一下雙指針法
? ? ? ? ? ? ? ? 我下面不止有一種方法,各個方法我想借著代碼來幫助你理解,在這里就不過多闡述
? ? ? ? ? ? ? ? 有時候碰見一些相似的題,也許它們所考查的方向其實大差不差,可以比對著理解哦
? ? ? ? 3.示例查驗
? ? ? ? ? ? ? ? 示例1和示例2:數組的大小和除數組前幾個元素外的其他元素并不重要
? ? ? ? 4.嘗試編寫代碼:
? ? ? ? ? ? ? ? (1)雙指針法
? ? ? ? ? ? ? ? ? ? ? ? 思路:準備兩個指針,一個放在數組的首位,一個放在數組的末尾,前面的指針查找等于val的數,后面的指針查找不等于val的數,兩個指針都找到之后就交換這兩個數,再將前面的指針后移一位,后面的指針前移一位,再重復上面的操作
? ? ? ? ? ? ? ? ? ? ? ? 當后面的指針比前面的指針靠前的時候,就退出循環,以下是完整代碼
class Solution {
public:int removeElement(vector<int>& nums, int val) {int p1=0,p2=nums.size()-1;//準備兩個指針while(p1<=p2){//當后面的指針小于前面的指針時if(nums[p1]!=val)p1++;//前面的指針查找等于val的數if(nums[p2]==val)p2--;//后面的指針查找不等于val的數if(p1<p2&&nums[p1]==val&&nums[p2]!=val){//如果滿足括號里面的條件,就進行交換swap(nums[p1],nums[p2]);//其實也不用非得交換,直接賦值也行,畢竟余下的元素不重要p1++;p2--;}}return p2+1;//返回數組中不等于val的數的數目}
};
? ? ? ? ? ? ? ? (2)快慢指針法
? ? ? ? ? ? ? ? ? ? ? ? 思路:也是準備兩個指針,兩個指針的起點都在數組的首位,其中快指針向后查找不等于val的值,查找到了之后,覆蓋慢指針指向的數,再將慢指針后移一位,快指針繼續查找
以下是完整代碼
class Solution {
public:int removeElement(vector<int>& nums, int val) {int slow=0;//慢指針for(int fast=0;fast<nums.size();fast++){//快指針if(nums[fast]!=val)nums[slow++]=nums[fast];}return slow;}
};
? ? ? ? ? ? ? ? (3)反骨法
? ? ? ? ? ? ? ? ? ? ? ? 思路:它說不讓用輔助存儲空間,你要不要用?要不要用?
? ? ? ? ? ? ? ? ? ? ? ? 當然可以使用,但是不建議,耍小聰明始終上不了大雅之堂哦
? ? ? ? ? ? ? ? ? ? ? ? 所以,看看就可以了,以下是完整代碼
class Solution {
public:int removeElement(vector<int>& nums, int val) {vector<int>res;//準備輔助存儲空間for(int& num:nums){//遍歷數組if(num!=val)res.push_back(num);//如果某個值不等于val,就放入res中}nums.swap(res);return nums.size();}
};