P168. 移除有序数组中的重复元素

https://algocasts.io/episodes/yRp3k6p4

老哥你好,我想问问这道题能不能用

if nums[i] != nums[i+1]:

这个判断条件来进行去重?
我尝试了一下好像写不出来,谢谢老哥

分享下我的思考:
因为我做3Sum那题的缘故(涉及到很多数组去重的东西)所以我就重新回顾了这道题
然后写的时候发现大家一般都是这样写的:
if nums[i] != nums[i-1]:
于是我就思考能不能用
if nums[i] != nums[i+1]:
这样的判断来写(理论上是一样的),后面发现总会出一些差错。
最后我发现其实问题的关键是在于p这个值的设定

p = 1的时候,是默认nums[0]是不重复的
然后我们每次更新nums[p], 都是使用index跑的较快的一个来进行更新,例如
nums[i],nums[i+1]中的 nums[i+1]
nums[i-1], nums[i]重的 nums[i]
不然的话,跑的慢的元素是无法遍历完整个数组的,所以会出现答案不完整的现象

    p = 1

    for i in range(1, len(nums)):
        if nums[i] != nums[i+1]:
            nums[p] = nums[i+1]
            p += 1

    return p

假如我们硬要用跑的慢的index来更新nums[p]
我们则要把p = 0, 且要在nums后面添加一个元素,以保证跑得慢的元素能遍历完整个nums

    nums.append(None)
    p = 0
   
    for i in range(len(nums)-1):
        if nums[i] != nums[i+1]:
            nums[p] = nums[i]
            p += 1
        
    return p

所以总体来说,无论你是使用p=0,p=1, 还是利用nums[i],nums[i+1],nums[i-1]来进行判重
只要保证更新指针能遍历完整个数组,能把不重复的元素全部记录,都是可以的

@Yifu_Chen

不必改变数组 nums(这样带来额外的操作时间和辅助空间),直接在循环结束时,把最后没有填充到前面的数字填充一下即可,Java 代码:

  public int removeDuplicates(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int p = 0, q = 0;
    for (; q < nums.length-1; ++q)
      if (nums[q] != nums[q+1])
        nums[p++] = nums[q];
    nums[p++] = nums[q]; // 增加这一条语句即可
    return p;
  }

nice!