In the Leetcode Remove Duplicates from Sorted Array II problem solution Given an integer array nums sorted in non-decreasing order, remove some duplicates in place such that each unique element appears at most twice. The relative order of the elements should be kept the same.
Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.
Return k after placing the final result in the first k slots of nums.
Do not allocate extra space for another array. You must do this by modifying the input array in place with O(1) extra memory.
Custom Judge:
The judge will test your solution with the following code:
int[] nums = […]; // Input array
int[] expectedNums = […]; // The expected answer with correct length
int k = removeDuplicates(nums); // Calls your implementation
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
If all assertions pass, then your solution will be accepted.
Example 1:
Input: nums = [1,1,1,2,2,3]
Output: 5, nums = [1,1,2,2,3,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).
Example 2:
Input: nums = [0,0,1,1,1,1,2,3,3]
Output: 7, nums = [0,0,1,1,2,3,3,,]
Explanation: Your function should return k = 7, with the first seven elements of nums being 0, 0, 1, 1, 2, 3 and 3 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).
Constraints:
- 1 <= nums.length <= 3 * 104
- -104 <= nums[i] <= 104
- nums is sorted in non-decreasing order.
Solution in C Programming
int removeDuplicates(int* nums, int numsSize){
int i, j, count = 0;
for(i = 1, j = 0; i < numsSize; i++){
if(nums[i] != nums[j]){ /*The 2 numbers are different*/
count = 0;
nums[++j] = nums[i];
}
else if(count == 0){ /*The 2 numbers are equal and it's the first time*/
count++;
nums[++j] = nums[i];
}
}
return j + 1;
}Solution in C++ Programming
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int res=0,c=0;
if(nums.size()<=2){
return nums.size();
}
int j=0;
int x=nums[0];int i;
for(i=0;i<nums.size();i++){
if(x!=nums[i]){
if(c<2){
res=res+c;// here we are adding to result if count of that number is lessthan or equal to 2
}
else{
res=res+2;//here we are considering that if frequency of element greater than 2 than also we have to conisder its result to count two
}
c=1;x=nums[i];
if(c<=2){
nums[j++]=nums[i];//here we are setting elements to the given array according to the question
}
}
else{
c++;
if(c<=2){
nums[j++]=nums[i];
}
}
}
nums.resize(j);//or understanding we resize vector to j && j is result
if(c<2){
res=res+c; // here we are considering for last elements
}
else{
res=res+2;
}
return res;
}
};Solution in Java Programming
class Solution {
public int removeDuplicates(int[] A) {
final int k = 2;
if (A == null || A.length <= k)
return A.length;
int left = k; // left: next index to place; right: next element to check
for (int right = k; right < A.length; right++) {
for (int i = 1; i <= k; i++) {
if (A[right] != A[left-i]) {
A[left++] = A[right];
break;
}
}
}
return left;
}
}Solution in Python Programming
class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
if n < 3:
return n
i , j = 1, 2
while j < n:
if nums[i-1] != nums[j]:
i += 1
nums[i] = nums[j]
j+= 1
return i+1Solution in C# Programming
public class Solution {
public int RemoveDuplicates(int[] nums)
{
int left = 1;
int currentlyProcessing = nums[0];
int groupCt = 1;
for (int i = 1; i < nums.Length; i++)
{
if (nums[i] == currentlyProcessing)
{
groupCt++;
if (groupCt > 2) // if streak goes over 2, stop advancing left pointer, continue
continue;
Swap(nums, left, i); // swap nums[i] with nums[left]
}
else // if move to new numbergroup, reset CurrentlyProcessing and groupCt
{
currentlyProcessing = nums[i];
groupCt = 1;
Swap(nums, left, i); // swap nums[i] with nums[left]
}
left++;
}
return left;
}
void Swap(int[] nums, int left, int i)
{
int temp = nums[left];
nums[left] = nums[i];
nums[i] = temp;
}
}Also read,