一斧散、題目
LeetCode-80. 刪除有序數(shù)組中的重復(fù)項(xiàng) II
鏈接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii/
難度：中等
給你一個(gè)有序數(shù)組 nums 严望，請(qǐng)你原地刪除重復(fù)出現(xiàn)的元素淹遵，使每個(gè)元素 最多出現(xiàn)兩次 杖剪，返回刪除后數(shù)組的新長(zhǎng)度。
不要使用額外的數(shù)組空間填硕，你必須在 原地 修改輸入數(shù)組 并在使用 O(1) 額外空間的條件下完成碧库。
說(shuō)明：
為什么返回?cái)?shù)值是整數(shù)涡贱，但輸出的答案是數(shù)組呢堪夭？
請(qǐng)注意愕把，輸入數(shù)組是以「引用」方式傳遞的拣凹，這意味著在函數(shù)里修改輸入數(shù)組對(duì)于調(diào)用者是可見(jiàn)的森爽。
你可以想象內(nèi)部操作如下:
// nums 是以“引用”方式傳遞的。也就是說(shuō)嚣镜，不對(duì)實(shí)參做任何拷貝
int len = removeDuplicates(nums);
// 在函數(shù)里修改輸入數(shù)組對(duì)于調(diào)用者是可見(jiàn)的爬迟。
// 根據(jù)你的函數(shù)返回的長(zhǎng)度, 它會(huì)打印出數(shù)組中 該長(zhǎng)度范圍內(nèi) 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
示例 1：
輸入：nums = [1,1,1,2,2,3]
輸出：5, nums = [1,1,2,2,3]
解釋：函數(shù)應(yīng)返回新長(zhǎng)度 length = 5, 并且原數(shù)組的前五個(gè)元素被修改為 1, 1, 2, 2, 3 菊匿。 不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素付呕。
示例 2：
輸入：nums = [0,0,1,1,1,1,2,3,3]
輸出：7, nums = [0,0,1,1,2,3,3]
解釋：函數(shù)應(yīng)返回新長(zhǎng)度 length = 7, 并且原數(shù)組的前五個(gè)元素被修改為 0, 0, 1, 1, 2, 3, 3 。 不需要考慮數(shù)組中超出新長(zhǎng)度后面的元素跌捆。
提示：
1 <= nums.length <= 3 * 10^4
-10^4 <= nums[i] <= 10^4
nums 已按升序排列
二徽职、解題思路
與一起學(xué)算法-26. 刪除有序數(shù)組中的重復(fù)項(xiàng)類似，采用快慢指針的方法佩厚。本題比較難的一點(diǎn)是要考慮明白要保留的元素的條件姆钉。
三、實(shí)現(xiàn)過(guò)程
c++
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int len = nums.size();
if (len <= 2) {
return len;
}
int slow = 2, fast = 2;
while (fast < len) {
if (nums[slow - 2] != nums[fast]) {
nums[slow] = nums[fast];
++slow;
}
++fast;
}
return slow;
}
};
PHP
class Solution {
/**
* @param Integer[] $nums
* @return Integer
*/
function removeDuplicates(&$nums) {
$len = count($nums);
if($len <= 2){
return $len;
}
$slow = 2;
$fast = 2;
while($fast < $len){
if($nums[$slow - 2] != $nums[$fast]){
$nums[$slow] = $nums[$fast];
++$slow;
}
++$fast;
}
return $slow;
}
}
JavaScript
/**
* @param {number[]} nums
* @return {number}
*/
var removeDuplicates = function(nums) {
var len = nums.length;
if(len <= 2){
return len;
}
var slow = 2,fast = 2;
while(fast < len){
if(nums[slow - 2] != nums[fast]){
nums[slow] = nums[fast];
++slow;
}
++fast;
}
return slow;
};
四、小結(jié)
- 時(shí)間復(fù)雜度：O(N)潮瓶，其中N是數(shù)組nums的長(zhǎng)度
- 空間復(fù)雜度：O(1)
