题目
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 1: 给定 nums = [1,1,1,2,2,3], 函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 你不需要考虑数组中超出新长度后面的元素。
示例 2: 给定 nums = [0,0,1,1,1,1,2,3,3], 函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。 你不需要考虑数组中超出新长度后面的元素。
算法
public class P80 {
public int removeDuplicates(int[] nums
) {
if(nums
.length
==0){
return 0;
}
int count
= 1;
int cur
= nums
[0];
int i
= 1;
int j
= 1;
while (j
<nums
.length
){
if(nums
[j
]==cur
){
if(count
<2){
if(i
!=j
){
swap(nums
,i
,j
);
}
j
++;
i
++;
count
++;
}else {
while(j
<nums
.length
&&nums
[j
]<=cur
){
j
++;
}
if(j
<nums
.length
){
cur
= nums
[j
];
swap(nums
,i
,j
);
i
++;
j
++;
count
= 1;
}
}
}else if(nums
[j
]>cur
){
cur
= nums
[j
];
swap(nums
,i
,j
);
i
++;
j
++;
count
= 1;
}
}
return i
;
}
private void swap(int[] nums
,int i
,int j
){
int tmp
= nums
[i
];
nums
[i
] = nums
[j
];
nums
[j
] = tmp
;
}
}
思路：
cur代表当前数字，count代表当前数字的个数，采用双指针法求解，慢指针i代表删除后的数组当前值，快指针j代表顺序遍历排序数组的指针。遍历当前nums[j] = = cur 2.1 count小于2时，若i、j不相等则交换下标为i、j的数字，i++，j++，count++，cur不变 2.2 count大于等于2时，则代表j处的值需要删除，j往后遍历找到一个大于cur的值nums[j]，cur = = nums[j]交换下标为i、j的数字i++，j++,count置1当nums[j],cur = = nums[j],若i、j不相等则交换下标为i、j的数字,i++，j++,count置1
算法2
class Solution {
public int removeDuplicates(int[] nums
) {
int i
= 0;
for (int n
: nums
)
if (i
< 2 || n
> nums
[i
-2])
nums
[i
++] = n
;
return i
;
}
}
leetcode思路：
也是双指针解法快指针顺序遍历满指针只有在当前值快指针指向的值n大于nums[i-2]时才会步进1
