題目描述 26. 刪除有序數(shù)組中的重復(fù)項(xiàng)
給你一個(gè)有序數(shù)組nums 牍汹，請(qǐng)你原地刪除重復(fù)出現(xiàn)的元素砂心，使每個(gè)元素 只出現(xiàn)一次 彻秆，返回刪除后數(shù)組的新長度楔绞。
不要使用額外的數(shù)組空間，你必須在原地修改輸入數(shù)組 并在使用額外空間的條件下完成唇兑。
說明:
為什么返回?cái)?shù)值是整數(shù)酒朵，但輸出的答案是數(shù)組呢?
請(qǐng)注意，輸入數(shù)組是以「引用」方式傳遞的扎附，這意味著在函數(shù)里修改輸入數(shù)組對(duì)于調(diào)用者是可見的蔫耽。
你可以想象內(nèi)部操作如下:
// nums 是以“引用”方式傳遞的。也就是說留夜，不對(duì)實(shí)參做任何拷貝
int len = removeDuplicates(nums);
// 在函數(shù)里修改輸入數(shù)組對(duì)于調(diào)用者是可見的匙铡。
// 根據(jù)你的函數(shù)返回的長度, 它會(huì)打印出數(shù)組中 該長度范圍內(nèi) 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
示例1
輸入：nums = [1,1,2]
輸出：2, nums = [1,2]
解釋：函數(shù)應(yīng)該返回新的長度 2 碍粥，并且原數(shù)組 nums 的前兩個(gè)元素被修改為 1, 2 鳖眼。不需要考慮數(shù)組中超出新長度后面的元素。
示例2
輸入：nums = [0,0,1,1,1,2,2,3,3,4]
輸出：5, nums = [0,1,2,3,4]
解釋：函數(shù)應(yīng)該返回新的長度 5 嚼摩， 并且原數(shù)組 nums 的前五個(gè)元素被修改為 0, 1, 2, 3, 4 钦讳。不需要考慮數(shù)組中超出新長度后面的元素。
提示：
- 0 <= nums.length <= 3 * 104
- -104 <= nums[i] <= 104
- nums 已按升序排列
思路1 刪除數(shù)組元素
我們可以對(duì)數(shù)組進(jìn)行遍歷枕面，記錄一個(gè)唯一值uniq=nums[0]愿卒。
- 當(dāng)遍歷的元素不等于該唯一值時(shí)，我們將唯一值指針右移膊畴。
- 當(dāng)遍歷的元素等于唯一值時(shí)掘猿，說明是重復(fù)元素，此時(shí)刪掉重復(fù)元素唇跨。
- 當(dāng)遍歷結(jié)束時(shí)稠通，得到新的數(shù)組，返回該數(shù)組長度即可买猖。
代碼實(shí)現(xiàn)
/**
* 刪除數(shù)組元素的方式
* @param {number[]} nums
* @return {number}
*/
var removeDuplicates = function (nums) {
if (nums == null || nums.length === 0)
return 0
let i = 1
while (i < nums.length) {
if(nums[i-1] === nums[i]) {
nums.splice(i, 1)
}else {
i++
}
}
return nums.length
};
思路2 不刪除數(shù)組元素
我們同樣可以用兩個(gè)指針slow = 0和fast = 1改橘，其中fast指針遍歷數(shù)組，slow指針指向需要被覆蓋的不重復(fù)元素的位置玉控。
- 當(dāng)判斷
nums[fast] !== nums[slow]的時(shí)候飞主，說明出現(xiàn)了不重復(fù)元素，此時(shí)進(jìn)行覆蓋nums[++slow] = nums[fast] - 當(dāng)判斷
nums[fast] === nums[slow]時(shí)候，說明是重復(fù)元素碌识，只需要將fast指針右移即可碾篡。 - 當(dāng)遍歷結(jié)束后，返回
slow指針的下一個(gè)位置（數(shù)組長度=指針位置+1）
代碼實(shí)現(xiàn)
/**
* 雙指針
* @param {number[]} nums
* @return {number}
*/
var removeDuplicates = function (nums) {
if (nums == null || nums.length === 0) {
return 0
}
const n = nums.length
let slow = 0, fast = 1
while (fast < n) {
if (nums[slow] !== nums[fast]) {
nums[++slow] = nums[fast]
}
fast++
}
return slow + 1
}
結(jié)語
由于思路2雙指針只是對(duì)數(shù)組元素進(jìn)行覆蓋筏餐，而非思路1中采用Array.splice()方法對(duì)數(shù)組元素進(jìn)行刪除开泽，效率極大提升，推薦使用魁瞪。
