#27 移除元素
思路
由于它實(shí)際調(diào)用接口的例子是圖上這樣感耙，輸出的限制就比較多喘沿。要求原地刪除val制跟，不能開新的數(shù)組來存進(jìn)行刪除操作后的數(shù)組，那么每次檢測(cè)到val就把它后面的所有數(shù)前移一位颗搂。
遍歷數(shù)組，每次檢測(cè)到val就將之后的數(shù)前推一位幕垦，然后計(jì)數(shù)count加1丢氢。
nums.lenth-count=輸出的數(shù)組長(zhǎng)度lenth傅联。
Case 1:沒有相鄰且等于val的數(shù)，那么正常運(yùn)行
Case 2:最后一位數(shù)等于val,隨著不斷地進(jìn)行這種粗糙的前移操作疚察，會(huì)從最后一個(gè)數(shù)copy出很多個(gè)等于val的值蒸走。解決辦法就是每次前移完成后將最后一位數(shù)覆蓋為101（因?yàn)関al是小于100的，不可能取到101）.
Case 3:存在兩個(gè)以上相鄰且等于val的數(shù)貌嫡，這種時(shí)候由于將后一個(gè)數(shù)前移到當(dāng)前操作的num[i]比驻，導(dǎo)致會(huì)漏掉這個(gè)相連且重復(fù)的數(shù)，解決辦法就是每次前移之后檢查num[i]岛抄，如果還等于val别惦，就從num[i]開始再執(zhí)行一次前移操作（套娃）
代碼
class Solution {
public:
? ? int removeElement(vector<int>& nums, int val) {
? ? ? ? int length,count=0;
? ? ? ? for (int i = 0; i < nums.size(); i++) {
? ? ? ? repeat:? if (nums[i]==val)
? ? ? ? ? {
? ? ? ? ? ? ? count++;
? ? ? ? ? ? ? for (int j=i; j<(nums.size()-1); j++)
? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? nums[j]=nums[j+1];
? ? ? ? ? ? ? }
? ? ? ? ? ? ? //case 1:the last number is val
? ? ? ? ? ? ? if (nums[nums.size()-1]==val)
? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? nums[nums.size()-1]=101;
? ? ? ? ? ? ? }
? ? ? ? ? ? ? //case 2:more than 2 near numbers are all equal to val then do the delete operation again
? ? ? ? ? ? ? //Actually I do not like "goto" ,it's dangerous ,but it's the first solution I thought out to deal with this
? ? ? ? ? ? ? //Pardon me....
? ? ? ? ? ? ? if (nums[i]==val)
? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? goto repeat;
? ? ? ? ? ? ? }
? ? ? ? ? }
? ? ? ? }
? ? ? ? length=nums.size()-count;
? ? ? ? return length;
? ? }
};
反思
1.這種前移操作是非常粗糙的，會(huì)導(dǎo)致一些BUG夫椭，有優(yōu)化的空間掸掸。在測(cè)試中我也遇到了尾數(shù)是val和有多個(gè)相連的val數(shù)的情況。由于我采用的是遍歷式的for循環(huán)益楼，針對(duì)這兩種情況就只能見招拆招打補(bǔ)丁猾漫，而不能從結(jié)構(gòu)設(shè)計(jì)上優(yōu)雅地去避免這兩種情況出錯(cuò)，有點(diǎn)尷尬感凤。
2.針對(duì)多個(gè)等于val的數(shù)相連的情況悯周，我采用的是每次前移之后都再次檢查當(dāng)前操作數(shù)，如果也為val陪竿，則再次執(zhí)行前移禽翼，相當(dāng)于是個(gè)套娃操作。為了減少代碼量（圖省事）族跛，雖然不情愿闰挡，我還是采用了"goto"語句，用起來倒是沒什么問題礁哄。原諒我长酗，goto真的很危險(xiǎn)。桐绒。夺脾。。茉继。咧叭。。
#977 有序數(shù)組的平方
思路
看到這個(gè)題之后的直接想法就是直接全部平方存到新數(shù)組里（操作)烁竭，然后再做一個(gè)排序菲茬，隨便什么排序都能滿足最基本的要求。
再看進(jìn)階要求，時(shí)間復(fù)雜度婉弹，平方操作是固定的睬魂，那么只能從這個(gè)排序方法上做文章。普通的排序復(fù)雜度在
镀赌，好一點(diǎn)的也要
汉买，達(dá)不到要求。但是注意到本題是一個(gè)非降序數(shù)列佩脊，即使有正有負(fù)蛙粘，那也有一個(gè)分界數(shù)，這讓我聯(lián)想到了歸并排序里的Merge操作威彰，所以我決定采用這種方法出牧。
首先遍歷找到分界數(shù)，然后從分界數(shù)的位置分割成兩個(gè)數(shù)組歇盼。
然后將兩個(gè)數(shù)組分別平方舔痕，一個(gè)從前往后，一個(gè)從后往前豹缀，兩個(gè)數(shù)組元素比較大小伯复，按順序歸并入新的數(shù)組。
代碼
class Solution {
public:
? ? vector<int> sortedSquares(vector<int>& nums) {
? ? ? ? int divide=0;
? ? ? ? int leftcount=0;
? ? ? ? int rightcount=0;
? ? ? ? int leftindex=0;
? ? ? ? int rightindex=0;
? ? ? ? int count=0;
? ? ? ? int i,j=0;
? ? //To find the index of the divide number
? ? ? ? for ( i=1 ; i<nums.size() ; i++ )
? ? ? ? {
? ? ? ? ? ? if ((nums[i]*nums[i-1])<=0)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? divide=i-1;
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? }
? ? // all 0
? ? ? ? if ((divide==0)&&(nums[nums.size()-1]<0))
? ? ? ? {
? ? ? ? ? ? divide=nums.size()-1;
? ? ? ? }
? ? // divide into two arrays
? ? ? ? int left[nums.size()];? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? int right[nums.size()];
? ? //initial left and right array
? ? ? ? for ( i=0 ; i< divide;i++)
? ? ? ? {
? ? ? ? ? ? left[i]=0;
? ? ? ? }
? ? ? ? for ( i=0 ; i< nums.size()-divide-1;i++)
? ? ? ? {
? ? ? ? ? ? right[i]=0;
? ? ? ? }
? ? ? ? for ( j=divide; j>=0 ; j--)
? ? ? ? {
? ? ? ? ? ? left[leftindex]=nums[j]*nums[j];
? ? ? ? ? ? leftindex++;
? ? ? ? }
? ? ? ? ? for ( i=divide+1 ; i<nums.size() ; i++)
? ? ? ? {
? ? ? ? ? ? right[rightindex]=nums[i]*nums[i];
? ? ? ? ? ? rightindex++;
? ? ? ? }
//Compare and merge
? ? ? ? for ( i=0; i<nums.size() ; i++)
? ? ? ? {
? ? ? ? ? if (rightcount<rightindex)
? ? ? ? ? {
? ? ? ? ? ? ? if (leftcount<leftindex)
? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? if (left[leftcount]<=right[rightcount])
? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? nums[i]=left[leftcount];
? ? ? ? ? ? ? ? ? ? ? leftcount++;
? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? nums[i]=right[rightcount];
? ? ? ? ? ? ? ? ? ? ? ? rightcount++;
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? else
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? nums[i]=right[rightcount];
? ? ? ? ? ? ? ? ? ? rightcount++;
? ? ? ? ? ? ? ? }
? ? ? ? ? }
? ? ? ? ? ? else
? ? ? ? ? ? {
? ? ? ? ? ? ? ? nums[i]=left[leftcount];
? ? ? ? ? ? ? ? leftcount++;
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? cout<<count<<' '<<leftcount<<' '<<rightcount;
? ? ? ? return nums;
? ? }
};
反思
這個(gè)歸并操作實(shí)現(xiàn)起來居然很艱難邢笙，主要是左右兩個(gè)數(shù)組的邊界情況把我繞暈了啸如。
內(nèi)存消耗沒辦法，如果是用最簡(jiǎn)單的平方加排序來做空間復(fù)雜度肯定會(huì)低很多氮惯。
不過我這個(gè)就屬于空間換時(shí)間了叮雳。
總的來說花了快兩個(gè)小時(shí)，寫出來的代碼比較爛妇汗，感覺歸并的判斷邏輯可以優(yōu)化帘不，數(shù)組的大小可以優(yōu)化。杨箭。寞焙。
眼睛看花了，就這樣吧先
先吃個(gè)海鮮燜面互婿，拜拜
