博客

题目

给你一个有序数组 nums ，请你原地删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例1

输入：nums = [1,1,2]
输出：2, nums = [1,2]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例2

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

解析

由于此题要求不使用额外数组空间，故只能考虑通过对原数组进行操作。



解法

//1.选取数组中一个元素num
//2.与数组中其他元素进行比较，判断是否相同
//3.如果相同，则往下比较，直至找到不同的元素或遍历完数组
//3.1 若出现的不同元素，则将该元素存至num元素的下一位，并
//3.2 若遍历完数组，

代码

常规解法

此解法利用嵌套循环，导致算法的时间复杂度增加，即为O(N*N)

int removeDuplicates(vector<int>& nums) {
    int idx = 0;
    int i = 0;
    if(nums.size() == 0) {
        return 0;
    }
    while(i < nums.size()) {
        int j = i + 1;
        for(;j < nums.size(); j++) {
            if(nums[i] != nums[j]) {
                break;
            }
        }
        if(j < nums.size()) {
            nums[++ idx] = nums[j];
            i = j;
            continue;
        }
        i++;
    }
    return ++idx;
}

优化解法

优化后的算法时间复杂度为O(N)

int removeDuplicates(vector<int>& nums) {
	  int len = 1;
	  int i, num;
	  if(nums.size() == 0) {
	      return 0;
	  }
	  num = nums[0];
	  for(i = 0; i < nums.size(); i++) {
	      if(nums[i] != num) {
	          nums[len] = nums[i];
	          num = nums[i];
	          len++;
	      }
	  }
	  return len;
}

总结

以上两段代码的解法是一样的，只是在思路上有稍微的不同，导致了算法时间复杂度产生了千差万别。往往在我们解决问题时，都是倾向于嵌套循环，但此题却采用了双指针去解决了嵌套循环的问题。