This is the 13th day of my participation in the First Challenge 2022

First, write first

I heard you’re still writing a two-layer for loop to solve the sum of two numbers?

LeetCode 2: Sum of two numbers transfer gate: the median of two sorted arrays, “most” technical solution!

LeetCode 第 3 题 : Longest loop transport gate: Horse-and-cart algorithm to solve longest loop! Manacher

LeetCode 4 题 conversion of string to integer (ATOI) : Solve ATOI with “foolish old man removing mountains” method, think clever!

Continue solving LeetCode, the longest public prefix

One of LeetCode’s “most classic” algorithm problems: the sum of three numbers

The sum of the nearest three numbers, wonderful

LeetCode: Valid parentheses

Question 9: Delete the duplicate items in the LeetCode array, for the interview, looking forward to your joining.

Today’s topic

Given a sorted array, you need to remove duplicate elements in place so that each element appears only once, returning the new length of the removed array.

Instead of using extra array space, you must modify the input array in place and do so with O(1) extra space. Example:

The sample1Nums = [1.1.2], the function should return the new length2, and the first two elements of the original array NUMs are modified to1.2. You don't need to worry about the element after the new length in the array. The sample2: given nums = [0.0.1.1.1.2.2.3.3.4], the function should return the new length5, and the first five elements of the original array NUMs are changed to0.1.2.3.4. You don't need to worry about the element after the new length in the array.Copy the code

Three, the analysis

For this problem, at first glance, I am still stunned. I can only operate in the original list, and the extra space complexity should be O(1). However, on second thought, it is also easier to do, because the original list has been ordered, and what we need to do is to remove or move the repeated elements to the back. Because the removeDuplicates function returns the maximum number of non-duplicates, as in example 1, which returns a value of 2, it prints the first two elements of the modified list. Here’s how it works:

  • My train of thought

  • Graphic algorithm

Fourth, the problem solving

  • My approach:

Time complexity: O(n) Space complexity: O(1

# My way
class Solution(object) :
	def removeDuplicates(self, nums) :
		""" :type nums: List[int] :rtype: int """
		n = len(nums)
		if n<=0:  # The length is less than or equal to 1
			return 0
		len_0 = 1
		for i in range(1,n): # for loops backwards
			ifnums[i] ! = nums[i-1]:
				nums[len_0] = nums[i]  # Data replacement
				len_0 = len_0 + 1 # Move the pointer back
		return len_0
Copy the code
  • Submit the results

Test data: 161 groups

Run time: 44-152ms Beat percentage :7.95-99.54%

  • The simplest way to do it

Use set set to remove list elements and directly change the original list time complexity: O(1) Space complexity: O(1)

class Solution() :
	def removeDuplicates(self,nums) :
		""" :type nums: List[int] :rtype: int """
		nums[:] = list(sorted(set(nums)))
		return len(nums)
Copy the code
  • Submit the results

Test data: 161 groups running time: 44-80ms beat percentage :22.34-99.54%

Five, doubt

First of all, I have determined today that the discussion of excellent algorithm, or optimal solution, is not based on the submission of results, but on the complexity of time and space and the difficulty of implementation. I will also pay attention to this point in the future algorithm, and analyze the complexity calculation.

Six, the concluding

Unconsciously, more than a month has passed, and say to yourself, if you and I still insist ~ insist and work hard: eventually get something.

Like to see the message forwarding, four support, the original is not easy. Ok, see you next time, I love the cat love technology, more love si si’s old cousin Da Mian ଘ(˙꒳˙)ଓ Di Di