LeetCode:数组（一）

本组囊括数组相关题目，难度不等：

27.Remove Element

题目描述：简单

注意不能使用额外空间。

解法一：

拷贝覆盖：，其实这也是双指针中的快慢指针思想。可以想到的是，我们设置一个新的数组下标ans初始为0，遍历原来的数组，当数组中的值等于val值时，则跳过该数字；当不等时，则拷贝并覆盖这个数字到新的数组并ans自增1，最后返回ans则能得到结果。

时间复杂度：O(n)，空间复杂度：O(1)

class Solution(object):
   def removeElement(self, nums, val):
       """
       :type nums: List[int]
       :type val: int
       :rtype: int
       """
       # 方法一： 拷贝覆盖,如果当前数组值不等于val，即让他拷贝并覆盖自己，下标+1；如果相等，则跳过该数字
       
       ans = 0
       for i in range(0,len(nums)):
           if nums[i] != val:
               nums[ans] = nums[i]
               ans += 1
       return ans

解法二：双指针（官方）

这里上面的情况的拷贝操作其实对于数组包含很少的要删除的元素的情况是多余的，考虑到题目描述中提到元素的顺序可以更改，可以考虑另一种思路：交换删除

主要思路是遍历数组nums，遍历指针为i，总长度为ans；

在遍历过程中如果出现数字与需要移除的值不相同时，则i自增1，继续下一次遍历；

如果相同的时候，则将nums[i]与nums[ans-1]交换，即当前数字和数组最后一个数字进行交换，交换后就少了一个元素，故而ans自减1；

时间复杂度：O(n)，空间复杂度：O(1)

1  # 方法二：交换移除
2         ans = len(nums)
3         for i in range(ans):
4             if nums[i] == val:
5                 nums[i] = nums[ans-1]
6                 ans = ans - 1

这里需要注意的是，虽然这种方法可以得到正确的新数组长度，但是没有本地操作nums，所有不是正确的解法。

26.Remove Duplicates from Sorted Array

题目描述：简单

解法一：双指针

类似上一题的思路，使用快慢指针办法：快指针去找没有重复的数字，慢指针记录没有重复的数字。

首先定义两个指针，一个p一个q，q隐式地放在循环中，p为慢指针，初始为0；q为快指针，初始为1。

其次判断条件nums[p] != nums[q] ,表示当前遍历的位置i和不重复集合的右边界不一样，那么肯定能放入不重复集合了。

时间复杂度：O(n)，空间复杂度：O(1)

 1 class Solution(object):
 2     def removeDuplicates(self, nums):
 3         """
 4         :type nums: List[int]
 5         :rtype: int
 6         """
 7         # 双指针，快慢指针办法：快指针去找没有重复的数字，慢指针记录没有重复的数字
 8         p = 0
 9         q = 1
10         while q < len(nums):
11             if nums[p] != nums[q]:
12                 nums[p+1] = nums[q]
13                 p += 1
14             q += 1        
15         return p+1

80.Remove Duplicates from Sorted Array II

题目描述：中等

解法一：双指针

和上一题类似，这题的提法变为了使得每个元素最多出现两次，其实我们可以把延伸到k次：

首先定义两个指针，一个p一个q，q隐式地放在循环中，p为慢指针，初始为k-1,q为快指针，初始为k。

其次这里题目要求每个元素最多出现k次,那么如果nums[p-k+1] != nums[q] 就可以保证不会存在连续的k个元素是值是重复的。

class Solution:
   def removeDuplicates(self, nums: List[int]) -> int:
       if not nums:
           return 0
       p = 1
       q = 2
       while q < len(nums):
           if nums[p-1] != nums[q]:
               nums[p+1] = nums[q]
               p += 1
           q += 1
       return p+1
       ''' 
       这里运用了同向指针思想，但还是套用的之前的快慢指针，
       若要求重复不超过K次，可让p=k-1,q=k
       让判定条件为nums[p-1]!=nums[q]
       '''