当前位置:网站首页>Leetcode: array (1)

Leetcode: array (1)

2020-11-10 10:44:18 Jesse-jia

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         '''

 

版权声明
本文为[Jesse-jia]所创,转载请带上原文链接,感谢