題目地址:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
題目:
給定一個(gè)排序數(shù)組,你需要在原地刪除重復(fù)出現(xiàn)的元素世澜,使得每個(gè)元素只出現(xiàn)一次贺嫂,返回移除后數(shù)組的新長(zhǎng)度翔怎。
不要使用額外的數(shù)組空間女责,你必須在原地修改輸入數(shù)組并在使用 O(1) 額外空間的條件下完成持灰。
示例 1:
給定數(shù)組 nums = [1,1,2],
函數(shù)應(yīng)該返回新的長(zhǎng)度 2, 并且原數(shù)組 nums 的前兩個(gè)元素被修改為 1, 2絮缅。
你不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素丁屎。
試題分析:
這道題是一道典型的有序數(shù)組操作題荠锭,要抓住三個(gè)要點(diǎn),一個(gè)是有序數(shù)組晨川,另一個(gè)是原地刪除证九,還有一個(gè)是不考慮超出新長(zhǎng)度后面的元素。
有序數(shù)組意味著通過(guò)O(n)的時(shí)間復(fù)雜度共虑,只需要循環(huán)一次就能夠剔除重復(fù)數(shù)字愧怜,要利用好有序這個(gè)特點(diǎn),當(dāng)有連續(xù)相等的數(shù)字時(shí)要做跳過(guò)處理妈拌。
原地刪除不使用額外空間拥坛,這就要求充分利用會(huì)被刪除的重復(fù)數(shù)字的位置。
綜上考慮下來(lái)尘分,可以使用快慢雙指針?lè)桨竵?lái)解該題猜惋,慢指針指向數(shù)組當(dāng)前循環(huán)過(guò)程中最后一個(gè)不重復(fù)的數(shù)值,快指針指向當(dāng)前循環(huán)體正在處理的數(shù)值音诫。當(dāng)比較兩個(gè)指針的時(shí)候這就會(huì)有兩種情況發(fā)生惨奕,當(dāng)慢指針和快指針指向的值相等的時(shí)候說(shuō)明快指針指向了重復(fù)的值,這時(shí)候慢指針不移動(dòng)竭钝,只對(duì)快指針進(jìn)行向后移動(dòng)梨撞;當(dāng)快指針和慢指針指向的數(shù)值不等的時(shí)候,說(shuō)明這個(gè)數(shù)字是要加到新數(shù)組里的香罐,這時(shí)候?qū)⒙羔樅笠苿?dòng)一位卧波,用快指針指向的值賦給慢指針后移后指向的值,這時(shí)你可能會(huì)說(shuō)直接覆蓋慢指針后的值不就造成數(shù)據(jù)被覆蓋了庇茫?答案是不會(huì)港粱,自己思考下,慢指針后面的數(shù)據(jù)會(huì)有兩種情況旦签,一種是和慢指針指向的值相等的重復(fù)數(shù)字查坪,還有一種是和慢指針不相等的數(shù)字,如果慢指針是有連續(xù)重復(fù)值則用快指針指向的不相等的值進(jìn)行覆蓋重復(fù)值位置宁炫,如果慢指針和快指針之間沒(méi)有重復(fù)的可覆蓋空間慢快指針指向的是兩個(gè)不相等的數(shù)字偿曙,則在慢指針后移一位后,其實(shí)相當(dāng)于快指針將值賦值給了自己羔巢,這點(diǎn)非常巧妙望忆,需要自己好好體會(huì)罩阵。
public int removeDuplicates(int[] nums) {
if(nums.length == 0){
return 0;
}
//i代表慢指針
int i = 0;
//j代表快指針
int j = 1;
for(;j<nums.length;j++){
if(nums[i] != nums[j]){
//慢指針指向的數(shù)字和快指針不相等的話(huà)則慢指針向后移動(dòng)一位
i++;
//將快指針指向的值賦值給慢指針指向的值,
// 1)如果數(shù)組內(nèi)的值是連續(xù)不相等启摄,則此時(shí)i=j快慢指針都指向同一個(gè)數(shù)值稿壁,相當(dāng)于原地賦值
// 2)如果連續(xù)相等后的第一個(gè)不相等,則將i++后j指向的第一個(gè)不相等的值賦值給i指向的值
nums[i] = nums[j];
}
}
//i是下標(biāo)值需要加1才是length
i++;
return i;
}
源碼路徑:com.monkey01.array.RemoveDuplicateFromSortedArray_26
配套測(cè)試代碼路徑:test目錄com.monkey01.array.RemoveDuplicateFromSortedArray_26Test