資訊專欄INFORMATION COLUMN
摘要：給定一個(gè)排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個(gè)元素只出現(xiàn)一次，返回移除后數(shù)組的新長度。不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用額外空間的條件下完成。聲明兩個(gè)指針，為快指針，為慢指針如果遇到相同的數(shù)，那么就跳過，。
給定一個(gè)排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個(gè)元素只出現(xiàn)一次，返回移除后數(shù)組的新長度。不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成。
劃重點(diǎn)：1.排序數(shù)組 2.原地刪除
錯(cuò)誤思路：
1.聲明一個(gè)tmp，初始就是nums[0]，用作被比較的對(duì)象
2.用tmp去和每一個(gè)后面的數(shù)去對(duì)比，相同的跳過，不同的，先把nums[j]設(shè)成tmp,然后j++，tmp變成不同的那個(gè)數(shù)
錯(cuò)誤點(diǎn)：
1.使用了新的內(nèi)存空間，是錯(cuò)誤的
2.tmp要和后面的數(shù)去比，tmp如果走到了最后一個(gè)，那么后面必然會(huì)產(chǎn)生越界。
3.tmp最后一定是一個(gè)和前面不同的數(shù)，這個(gè)數(shù)不參與比較，那么一定不會(huì)被覆蓋寫入數(shù)組
比如{1,1,2,2,3,3}->{1,2,2,2,3,3}
public static int removeDuplicates(int[] nums)
{
int i = 0, j = 0;
int tmp = nums[0];
for(i = 1; i < nums.length; i++)
{
if(nums[i] == tmp)
{
continue;
}
else
{
nums[j] = tmp;
tmp = nums[i];
j++;
}
}
System.out.println(j+1);
return j+1;
}
思路：
要求原地刪除，那么一定使用快慢指針進(jìn)行元素的覆蓋操作。
聲明兩個(gè)指針，i為快指針，j為慢指針
如果遇到相同的數(shù)，那么就跳過，i++。
如果遇到不同的數(shù)，將這個(gè)值的下一個(gè)數(shù)給替換成這個(gè)不一樣的值。
public static int removeDuplicates(int[] nums)
{
int i = 0, j = 0;
for(i = 1; i < nums.length; i++)
{
if(nums[j] == nums[i])
{
continue;
}
else
{
j++;
nums[j] = nums[i];
}
}
System.out.println(j+1);
return j+1;
}
代碼寫的不夠優(yōu)雅，因?yàn)榕袛嘞嗟热缓骳ontinue是沒有必要的，優(yōu)化一下：
public static int removeDuplicates(int[] nums)
{
int j = 0;
for(int i = 1; i < nums.length; i++)
{
if(nums[j] != nums[i])
{
j++;
nums[j] = nums[i];
}
}
return j+1;
}
復(fù)雜度分析：
遍歷一遍，時(shí)間復(fù)雜度o(n)
空間復(fù)雜度，o(1)
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/77840.html
摘要：給定一個(gè)排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個(gè)元素最多出現(xiàn)兩次，返回移除后數(shù)組的新長度。正確思路對(duì)于每一個(gè)元素，都進(jìn)行移動(dòng)?；蛘弑容^不到最后一個(gè)對(duì)象。 給定一個(gè)排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個(gè)元素最多出現(xiàn)兩次，返回移除后數(shù)組的新長度。不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成。 錯(cuò)誤思路：由26題跳過一個(gè)的思...
摘要：題目比較簡單，就是找出數(shù)組不重復(fù)的數(shù)字，返回不重復(fù)的數(shù)字個(gè)數(shù)。無需刪除重復(fù)數(shù)字，只需要保證數(shù)組的前位為不重復(fù)的個(gè)數(shù)字即可代碼如下 Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.Do not all...
摘要：題目要求從有序鏈表中刪除重復(fù)的數(shù)字，并且返回刪除后的頭結(jié)點(diǎn)例如輸入鏈表為返回這題和相似，只是數(shù)據(jù)結(jié)構(gòu)從數(shù)組變成了鏈表若還有更好的思路，請(qǐng)多多指教想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾 題目要求： 從有序鏈表中刪除重復(fù)的數(shù)字，并且返回刪除后的頭結(jié)點(diǎn)例如輸入鏈表為1->1->2,返回1->2 這題和leetcode26相似，只是數(shù)據(jù)結(jié)構(gòu)從數(shù)組變成了鏈表 /*...
摘要：雙指針法復(fù)雜度時(shí)間空間思路我們可以將不重復(fù)的序列存到數(shù)列前面，因?yàn)椴恢貜?fù)序列的長度一定小于等于總序列，所以不用擔(dān)心覆蓋的問題。代碼雙指針法復(fù)雜度時(shí)間空間思路思路和上題一樣，區(qū)別在于記錄前兩個(gè)遍歷到的數(shù)字來幫助我們判斷是否出現(xiàn)了第三遍。 Remove Duplicates from Sorted Array I Given a sorted array, remove the dupl...
摘要：思路與代碼其實(shí)在這里我們?nèi)匀谎永m(xù)中的思路。在遇到非重復(fù)值以及非多余的重復(fù)值時(shí)，將數(shù)值移動(dòng)到當(dāng)前記錄的下標(biāo)上。保證該下標(biāo)前的值均為滿足題目條件的值。第一次我使用了來記錄某個(gè)值出現(xiàn)的次數(shù)。 題目要求 Follow up for Remove Duplicates: What if duplicates are allowed at most twice? For example, Giv...
閱讀 1023·2023-04-25 23:50
閱讀 2173·2021-11-19 09:40
閱讀 668·2019-08-30 13:50
閱讀 2783·2019-08-29 17:11
閱讀 1098·2019-08-29 16:37
閱讀 3081·2019-08-29 12:54
閱讀 2859·2019-08-28 18:17
閱讀 2724·2019-08-26 16:55
