Description#
Given a sorted array nums, remove the duplicates in-place such that each element appears only once and returns the new length.
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
Example 1:
Given nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.
It doesn't matter what you leave beyond the returned length.
Example 2:
Given nums = [0,0,1,1,1,2,2,3,3,4],
Your function should return length = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It doesn't matter what you leave beyond the returned length.
Note:
Why is the returned value an integer but your answer is an array?
Note that the input array is passed in by reference, which means a modification to the input array will be known to the caller as well.
Internally you can think of this:
// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);
// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
print(nums[i]);
}
Approach#
- Traverse the array from the end. If the current element is the same as the previous one, move the array one position forward starting from the current element.
int removeDuplicates(int* nums, int numsSize){
int now_size = numsSize;//record the size of the array
for(int i=numsSize-1;i>0;i--) {
if(nums[i-1] == nums[i]) {//duplicate element found
now_size--;//decrement the size of the array
for(int j=0;j<numsSize-i-1;j++)//move the array forward
nums[i+j] = nums[i+j+1];
}
}
return now_size;
}
Follow-up#
- Traverse the array and set the repeated elements to the maximum or minimum value, and record the number of repetitions. The size of the new array is the original size minus the number of repetitions.
- Bubble sort the original array.
void exchange(int* num1,int* num2) {
int num = *num1;
*num1 = *num2;
*num2 = num;
}
int removeDuplicates(int* nums, int numsSize){
int delete_nums = 0;
for(int i=1;i<numsSize;i++) {
if(nums[i] == nums[i-1]) {
delete_nums++;
nums[i-1] = 0x7fff;
}
}
for(int i=0;i<numsSize;i++) {
for(int j=numsSize-1;j>i;j--) {
if(nums[j] < nums[j-1])
exchange(nums+j,nums+j-1);
}
}
return numsSize-delete_nums;
}
Follow-up 2#
- Since the array is sorted, each element in the final array is unique and in increasing order. Therefore, the first element does not need to be moved. Starting from the second element, traverse the array and if the current element is greater than the previous one, swap it with the second element, and then continue with the third element.
void exchange(int* num1,int* num2) {
int num = *num1;
*num1 = *num2;
*num2 = num;
}
int removeDuplicates(int* nums, int numsSize){
if(numsSize < 2)
return numsSize;
for(int now = 1,last_find = 1;;now++) {//current position
for(int find = last_find;;find++) {//pointer for searching
if(find >= numsSize)//search ends
return now;
if(nums[find] > nums[now-1]) {//specified element found
if(find != now)
exchange(nums+now,nums+find);
last_find = find + 1;//next search starts from the next position
break;
}
}
}
}
- This time the efficiency is much higher than before, and each swap is necessary.