LeekCode面试经典150题之删除有序数组中的重复项

LeekCode面试经典150题之删除有序数组中的重复项

本篇博文我将针对删除有序数组中的重复项问题（I,II)，给出一些解决的方法。两个问题我将分开进行讲解。有些方法是我自己想的（所以有不合理的地方很乐意与大家一起讨论），有些方法是参照的之前的博文中的。本片博文我们还引进了一种新的方法：快慢指针法

一、题目1 ：

题目描述：

给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k。去重后，返回唯一元素的数量 k。

nums 的前 k 个元素应包含 排序后 的唯一数字。下标 k - 1 之后的剩余元素可以忽略。

分析：这是移到删除元素的题目。我们可以采用遍历数组，然后直接求每个元素的出现次数，将出现多次的元素删掉。这种方法我在这个题目里面不给出具体的代码。在下面的拿到题目里面会具体给出代码。可以进行参照。还可以使用之前的博文中用到的栈的思想来解决（之前用到栈的思想解决的问题），还可以用我们今天重点要介绍的快慢指针法。接下来我会一一介绍。

1.栈的思想的解决方法：

defremoveDuplicates(self,nums):""" :type nums: List[int] :rtype: int """stack_pointer=0length=len(nums)foriinrange(length-1):ifnums[i]!=nums[i+1]:nums[stack_pointer]=nums[i]stack_pointer+=1ifi==length-2:nums[stack_pointer]=nums[i+1]returnstack_pointer+1

这里我们判断数组中的元素，如果当前元素和后面那个元素不一样话，我们就把当前的元素压入栈中，如果相同的话会直接跳到后一个元素。若现在已经是最后一个元素的话，就直接将其压入栈中。
这里我想在进一步解释一下，为什么是最后一个元素就可以直接压入栈中：因为在倒数第二个元素的时候，我们已经判断了倒数第二个数和倒数第一个数是否相等，如果不相等的话，那么这两个数都应该压入栈中，那么到最后一个数的时候直接将它压入栈中是没有问题的。如果他们不相等，那么我们不会将倒数第二数压入栈中，而是会直接来到倒数第一个数，所以将倒数第一个压入栈中也是合理的。其实从上面我们可以看出，为我们在每次压入的都是一串相同的数中的最后一个。

2.快慢指针法

defremoveDuplicates(self,nums):""" :type nums: List[int] :rtype: int """slow,fast=0,1whilefast<len(nums):ifnums[slow]!=nums[fast]:slow+=1nums[slow]=nums[fast]fast+=1returnslow+1

在这个方法里面，我们给定快慢两个指针。快的指针总是往后移动，直至移动到和当前慢指针所指的数不一样的时候，我们就将慢指针往后移动一个单位，再将这个不一样的数填入到慢指针当前所指的位置。然后快指针继续往后移动，重复这个操作。最后返回的数组长度就是慢指针+1。这是因为慢指针从零开始，所以+1才是数组的真实长度。

二、题目二：

题目描述：

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

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

分析：这个题目和刚才那个题目的思路基本一致，但是又比之前的那个题目更难了。这里我们需要控制最多能够重复的次数，并且必须要在原地进行，要在额外空间为 O(1) 下完成。下面我将介绍四种方法。除了第一种方法比较暴力，其他的方法的核心思想其实是共通的。当然这里也包含了栈的方法和快慢指针法，供大家参考学习。

1.暴力方法：

defremoveDuplicates(self,nums):""" :type nums: List[int] :rtype: int """foriinnums:whilenums.count(i)>2:nums.remove(i)returnlen(nums)

这种方法效率很低，但是也能够完成题目的要求。核心思想就是对数组中的每个数进行计数，如果数量大于2就删除数组中碰到的第一个这个数。用这种方式就能够达到题目的要求了。如果要求的数量不是2的话，我们直接将while nums.count(i)>2这里的2改成要求的数量即可。

2.快慢指针法：

defremoveDuplicates(self,nums):""" :type nums: List[int] :rtype: int """iflen(nums)<=2:returnlen(nums)slow=1fast=2whilefast<len(nums):ifnums[fast]!=nums[slow-1]:slow+=1nums[slow]=nums[fast]fast+=1returnslow+1

这里和之前不一样的是，两个指针要从1和2开始，然后我们需要判断快指针所指的和慢指针的前面那个是否相同，如果相同说明快指针后面可能还有和它相同的，因此我们要将快指针后移，直至快指针指向的不是和慢指针前面的数相同的数，我们就将慢指针后移，然后将快指针当前所指的数赋给慢指针。后面重复此流程。
这里说一下为什么这样做能够控制每个数重复不超过两次 ：因为数组是有序的，因此要想快指针与慢指针之前的指针指向的数是相同的，除非慢指针当前所指的数也是相同的。这样慢指针加上慢指针前面的那个数，者两个是六十相同的了，那么慢指针的下一个位置需要指向一个不一样的数，这个数我们通过快指针找到了。
在这种方法下，如果我们要控制的最多出现次数变化的话，我们可以通过改变快慢指针的初始位置，和每次与快指针比较的数的位置来实现。

3.栈的方法

defremoveDuplicates(self,nums):""" :type nums: List[int] :rtype: int """stack_pointer=1forxinnums[2:]:ifx!=nums[stack_pointer-1]:stack_pointer+=1nums[stack_pointer]=xreturnmin(stack_pointer+1,len(nums))

在栈的方法下，我们不需要对于数组的零号元素进行判断，因为不论再怎样它都会留下。因此我们的栈顶指针要从1开始。然后我们要判断从数组的第三个位置开始是否与当前栈顶指针指向的前一个位置的数相同，如果相同，那我们找到数组的下一个位置，直至找到与其不同的数，我们就把它放到栈顶指针的下一个位置。然后我们最后返回当前栈顶指针+1和数组长度这两者之间的最小值。

4.计数法

defremoveDuplicates(self,nums):""" :type nums: List[int] :rtype: int """index=count=1foriinrange(1,len(nums)):ifnums[i]==nums[i-1]:count+=1else:count=1ifcount<=2:nums[index]=nums[i]index+=1returnindex

对于这类问题，我们很容易想到要对每个数字重复的次数进行计数。根据重复次数的不同对数字进行不同的操作。
初始计数器为1，如果当前的数字和后一个数字相同，计数器加一。若当前的次数小于等于2的话，会继续往将当前的数赋给index指针所指的数，并且index指针后移。（赋值给index指针的数，都是确定了会保留下来的数）如果大于计数器大于2的话不会管它，会继续往后读取数字，直至读到新的相邻的相同的数，重复上面的操作。因为每次给index位置赋值的时候，index都会往后移动，所以最后返回index即可。

以上就是本次博文的所有内容，如果有什么问题，欢迎来和我讨论。