Delete duplicates in sorting array
Given a sort array, you need to delete duplicate elements in place so that each element appears only once, returning the new length of the array after removal.
Do not use extra array space, you must modify the input array in place and do so with O(1) extra space.
Example 1:
Given array nums = [1,1,2]
The function should return a new length of 2, and the first two elements of the original array nums are modified to 1, 2.
You don't need to think about the elements in the array that follow the new length.
Example 2:
Given nums = [0,0,1,1,1,2,2,3,3,4],
The function should return a new length of 5, and the first five elements of the original array nums are modified to 0, 1, 2, 3, 4.
You don't need to think about the elements in the array that follow the new length.
Iterate through the array, delete the current number if it is the same as the previous one, and move the subsequent array elements forward.
Java
public static int removeDuplicates(int[] nums) {
if (nums == null || nums.length == 0||nums.length==1)
return nums.length;
int current_location = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[current_location] == nums[current_location - 1]) {
for (int j = current_location; j < nums.length - 1; j++) {
nums[j] = nums[j + 1];
} else {
current_location++;
}
}
return current_location;
}C++
class Solution
{
public:
int removeDuplicates(vector<int>&nums)
{
if(nums.size()==0||nums.size()==1)return nums.size();
int current_location=1;
for(int i=1; i<nums.size(); i++)
{
if(nums[current_location]==nums[current_location-1])
{
for(int j=current_location; j<nums.size()-1; j++)
{
nums[j]=nums[j+1];
}
}
else
{
current_location++;
}
}
return current_location;
}
};Python
The next group failed because it timed out. To be improved.
class Solution(object):
def removeDuplicates(self, nums):
if len(nums) == 0 or len(nums) == 1:
return len(nums)
current_position = 1
for i in range(len(nums)):
if nums[current_position] == nums[current_position - 1]:
for j in range(current_position, len(nums) - 1):
nums[j] = nums[j + 1]
else:
current_position += 1
if current_position >= len(nums):
break
return current_position
stay online See more clever algorithm, the whole time complexity is only O(n), it mainly uses two coordinates i and j, one is faster, the other is slower, the following is its code, learning.
public int removeDuplicates(int[] nums) {
if (nums.length == 0) return 0;
int i = 0;
for (int j = 1; j < nums.length; j++) {
if (nums[j] != nums[i]) {
i++;
nums[i] = nums[j];
}
}
return i + 1;
}