資訊專欄INFORMATION COLUMN
摘要：給定一個排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個元素最多出現(xiàn)兩次，返回移除后數(shù)組的新長度。正確思路對于每一個元素，都進(jìn)行移動?；蛘弑容^不到最后一個對象。
給定一個排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個元素最多出現(xiàn)兩次，返回移除后數(shù)組的新長度。不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成。
錯誤思路：
由26題跳過一個的思路，很自然的聯(lián)想到跳過2個即可。但是對于{0，0,1,1,1,1,2,3,3}這種情況，最后一個3無法被放到前面去，結(jié)果是{0,0,1,1,2,3,2,3,3}，這是因為錯誤代碼將第一個不同的值移動到正確位置以后，下一個和剛被移動的這個值比對如果相同的話，是要等待下一次移動的，而下一次已經(jīng)到了數(shù)組末尾，不再進(jìn)行移動操作。
所以增加針對最后一個元素的處理（因為我只想到了最后一個元素可能和剛被移動的元素相同的情況），但是又引發(fā)了一個bug，即{1,1,1,2,2,3}->{1,1,2,2,3,3},當(dāng)全部移動完成后，我會多帶帶去比較最后一個元素是否和剛被移動的相同，相同的話，直接放到剛被正確安放的元素后，這樣就導(dǎo)致了重復(fù)數(shù)據(jù)的出現(xiàn)。
public static int removeDuplicates(int[] nums)
{
int i = 0, j = 0, count=1;
for(i = 1; i < nums.length; i++)
{
if(nums[i] != nums[j])
{
if (count >= 2)
{
j = j + 2;
nums[j] = nums[i];
}
else
{
j = j + 1;
nums[j] = nums[i];
}
count = 1;
}
else
{
count++;
}
}
if (nums[nums.length - 1] == nums[j])
{
j = j + 1;
nums[j] = nums[nums.length - 1];
}
System.out.println(j+1);
return j+1;
}
正確思路：
public int removeDuplicates(int[] nums)
{
int i = 0, j = 0, count=1;
for(i = 1; i < nums.length; i++)
{
if(nums[i] == nums[i-1])
{
count++;
}
else
{
count = 1;
}
if (count <= 2)
{
j = j + 1;
nums[j] = nums[i];
}
}
System.out.println(j+1);
return j+1;
}
1.對于每一個元素，都進(jìn)行移動。
2.計算相同的個數(shù)，相同的數(shù)量在2個以上時，就不進(jìn)行移動
3.不是比較nums[i]和nums[i+1]，因為這樣會導(dǎo)致溢出，參見26題的錯誤思路?；蛘弑容^不到最后一個對象。
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/77854.html
摘要：給定一個排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個元素只出現(xiàn)一次，返回移除后數(shù)組的新長度。不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組并在使用額外空間的條件下完成。聲明兩個指針，為快指針，為慢指針如果遇到相同的數(shù)，那么就跳過，。 給定一個排序數(shù)組，你需要在原地刪除重復(fù)出現(xiàn)的元素，使得每個元素只出現(xiàn)一次，返回移除后數(shù)組的新長度。不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組...
摘要：思路與代碼其實在這里我們?nèi)匀谎永m(xù)中的思路。在遇到非重復(fù)值以及非多余的重復(fù)值時，將數(shù)值移動到當(dāng)前記錄的下標(biāo)上。保證該下標(biāo)前的值均為滿足題目條件的值。第一次我使用了來記錄某個值出現(xiàn)的次數(shù)。 題目要求 Follow up for Remove Duplicates: What if duplicates are allowed at most twice? For example, Giv...
摘要：雙指針法復(fù)雜度時間空間思路我們可以將不重復(fù)的序列存到數(shù)列前面，因為不重復(fù)序列的長度一定小于等于總序列，所以不用擔(dān)心覆蓋的問題。代碼雙指針法復(fù)雜度時間空間思路思路和上題一樣，區(qū)別在于記錄前兩個遍歷到的數(shù)字來幫助我們判斷是否出現(xiàn)了第三遍。 Remove Duplicates from Sorted Array I Given a sorted array, remove the dupl...
摘要：思路原數(shù)組長度為，則返回原數(shù)組長度不為，則至少有個元素。將所有不重復(fù)的數(shù)值賦給，而當(dāng)和相等時，不做處理。最后返回的就是不同元素的個數(shù)，也是新數(shù)組的長度。只有在時，才對賦值。注意，每次初始化的時候要分兩種情況，這就意味著從的時候開始遍歷。 Remove Duplicates from Sorted Array I Problem Given a sorted array, remove ...
摘要：題目要求翻譯將鏈表中重復(fù)的元素全部刪除，返回新的頭結(jié)點。相比于，這里將重復(fù)的元素全部刪除。除此以外，我們還需要知道重復(fù)元素的前一個值和重復(fù)元素的最后一個值。如果存在重復(fù)值，則跳過重復(fù)值后，前節(jié)點不變，否則前節(jié)點跟隨后節(jié)點同時向后移動。 題目要求 Given a sorted linked list, delete all nodes that have duplicate number...
閱讀 2283·2021-09-07 09:58
閱讀 3473·2019-08-30 14:07
閱讀 1353·2019-08-29 12:32
閱讀 723·2019-08-29 11:06
閱讀 3745·2019-08-26 18:18
閱讀 3809·2019-08-26 17:35
閱讀 1440·2019-08-26 11:35
閱讀 671·2019-08-26 11:35
