# Leetcode: array (1)

2020-11-10 10:44:18

This group covers array related topics , The difficulty is not the same ：

## 27.Remove Element

Title Description ： Simple Be careful not to use extra space .

### Solution 1 ：

Copy overlay ：, In fact, this is also the idea of fast and slow pointer in double pointer . So here's what you can think about , We set a new array index ans For the initial 0, Traverse the original array , When the value in the array is equal to val When the value of , Then skip the number ; When it doesn't wait , Copy and overlay the number to the new array and ans Self increasing 1, Finally back to ans Then you get the result .

Time complexity ：O(n), Spatial complexity ：O(1)

``` 1 class Solution(object):
2     def removeElement(self, nums, val):
3         """
4         :type nums: List[int]
5         :type val: int
6         :rtype: int
7         """
8         #  Method 1 ：  Copy overlay , If the current array value is not equal to val, Let him copy and cover himself , Subscript +1; If equal , Then skip the number
9
10         ans = 0
11         for i in range(0,len(nums)):
12             if nums[i] != val:
13                 nums[ans] = nums[i]
14                 ans += 1
15         return ans```

### Solution 2 ： Double pointer （ official ）

The copy operation in the above case is redundant when the array contains few elements to be deleted , Considering that the order of the elements mentioned in the title description can be changed , You can think of another way of thinking ： Swap delete

The main idea is to traverse arrays nums, The traversal pointer is i, The total length of ans;

During traversal, if the number is different from the value to be removed , be i Self increasing 1, Go on to the next traversal ;

If at the same time , Will nums[i] And nums[ans-1] In exchange for , That is, the current number is exchanged with the last number in the array , After the exchange, one element is missing , so ans Self reduction 1;

Time complexity ：O(n), Spatial complexity ：O(1)

```1  #  Method 2 ： Swap remove
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```

What needs to be noted here is , Although this method can get the correct new array length , But there is no local operation nums, Not all solutions are correct .

## 26.Remove Duplicates from Sorted Array

Title Description ： Simple ### Solution 1 ： Double pointer

Similar to the previous question , Use the fast and slow pointer method ： Quick pointer to find the number that doesn't repeat , Slow pointer records no duplicate numbers .

First define two pointers , One p One q,q Implicitly in a loop ,p For slow pointer , For the initial 0;q For fast pointer , For the initial 1.

Second, judge the condition nums[p] != nums[q] , Represents the current traversal position i It's not the same as the right boundary of a non repeating set , Then it must be able to put in the non repeating set .

Time complexity ：O(n), Spatial complexity ：O(1)

``` 1 class Solution(object):
2     def removeDuplicates(self, nums):
3         """
4         :type nums: List[int]
5         :rtype: int
6         """
7         #  Double pointer , Quick and slow pointer method ： Quick pointer to find the number that doesn't repeat , Slow pointer records no duplicate numbers
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

Title Description ： secondary ### Solution 1 ： Double pointer

It's similar to the last question , The formulation of this problem is changed to make each element appear twice at most , In fact, we can extend it to k Time ：

First define two pointers , One p One q,q Implicitly in a loop ,p For slow pointer , For the initial k-1,q For fast pointer , For the initial k.

Secondly, the title requires that each element appear at most k Time , So if nums[p-k+1] != nums[q] To ensure that there is no continuous k Elements are values that repeat .

``` 1 class Solution:
2     def removeDuplicates(self, nums: List[int]) -> int:
3         if not nums:
4             return 0
5         p = 1
6         q = 2
7         while q < len(nums):
8             if nums[p-1] != nums[q]:
9                 nums[p+1] = nums[q]
10                 p += 1
11             q += 1
12         return p+1
13         '''
14          The idea of the same direction pointer is used here , But it's still the same as before ,
15          If required to repeat no more than K Time , Allowing p=k-1,q=k
16          Let the condition be nums[p-1]!=nums[q]
17         '''```