I tried LeetCode every day 26. Remove Duplicates from Sorted Array (Python, Go)

Introduction

@Ishishow is running a free English word site E-tan.

I would like to work on letcode every day to improve my ability as a programmer and give my own way of solving it.

What is Leetcode

leetcode.com This is the practice of coding interviews for software developers. A total of more than 1,500 coding questions have been posted, and it seems that the same questions are often asked in actual interviews.

Introduction to golang + algorithm I will solve it with go and Python to strengthen the brain. (Python is weak but experienced)

8th question (problem 26)

26. Remove Duplicates from Sorted Array

--Problem content (Japanese translation)

Specify a sorted array * nums , each element will only be displayed 1 * times , and duplicate [ in place **](https: // en. Delete it at wikipedia.org/wiki/In-place_algorithm).

Do not allocate extra space for another array. O (1) needs to be used ** and ** modified ** in the input array in-place ** ..

** Clarification: **

Don't know why the answer is an array when the return value is an integer?

Note that the input array is passed by ** reference **. This means that changes to the input array will be visible to the caller as well.

Internally, you can think about this.

//nums are passed by reference. (That is, without making a copy)
int len = removeDuplicates（nums）;

//Changes to nums in the function are known to the caller.
//Prints the first len element using the length returned by the function.
for（int i = 0; i <len; i ++）{
    print（nums [i]）;
}

Example 1:

  Input: nums = [1,1,2]
  Output: 2, nums = [1,2]
  Explanation: Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the returned length.

Example 2:

  Input: nums = [0,0,1,1,1,2,2,3,3,4]
  Output: 5, nums = [0,1,2,3,4]
  Explanation: Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively. It doesn't matter what values are set beyond the returned length.

Tip 1

An important point to focus on in this issue is the sorted input array. As far as overlapping elements are concerned, what are their positions in the array when a particular array is sorted? See the image above for the answer. If you know the position of one of the elements, do you know the position of all the overlapping elements?

Tip 2

The array needs to be modified in-place, and the final array size can be smaller than the input array size. Therefore, we need to use the two-pointer approach here. One keeps track of the current elements of the original array, and the other keeps track of only unique elements.

Tip 3

Basically, once an element is found, you need to ** bypass ** its duplication and move on to the next unique element.

Way of thinking

1. Create a new index (nw_index)

2. Turn the loop len (nums) times and proceed as it is if it overlaps

3. If there are no duplicates, substitute that value for the new index number.

4. The return value returns the length, so add 1

--Answer code

  class Solution(object):
      def removeDuplicates(self, nums):
          nw_index = 0
          for i in range(len(nums)):
              if nums[nw_index] != nums[i]:
                  nw_index +=1
                  nums[nw_index] = nums[i]
          return (nw_index + 1)

--I'll write it in Go too!

func removeDuplicates(nums []int) int {
	nw_index := 0
	for _, num := range nums {
		if nums[nw_index] != num {
			nw_index++
			nums[nw_index] = num
		}
	}

	return (nw_index + 1)
}

Another solution

def removeDuplicates(self, nums):
    nums[:] = sorted(set(nums))
    return len(nums)

Procedure explanation

Convert to set type (set type) with set ()

What is a set type?

The set type is a collection of non-overlapping elements (elements that do not have the same value, unique elements), and can perform set operations such as union, intersection, and difference.

Since set is a set, the order will be messed up, so use the sorted function to return it in ascending order.

Assign a reference to nums [:]. The reason why nums = is not set here is that a new object is created and memory is not consumed.