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)

  1. 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? img

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.

Recommended Posts

I tried LeetCode every day 26. Remove Duplicates from Sorted Array (Python, Go)
I tried LeetCode every day 21. Merge Two Sorted Lists (Python, Go)
I tried LeetCode every day 108. Convert Sorted Array to Binary Search Tree (Python, Go)
I tried LeetCode every day 167. Two Sum II --Input array is sorted (Python, Go)
I tried LeetCode every day 7. Reverse Integer (Python, Go)
I tried LeetCode every day 112. Path Sum (Python, Go)
I tried LeetCode every day 20. Valid Parentheses (Python, Go)
I tried LeetCode every day 136. Single Number (Python, Go)
I tried LeetCode every day 118. Pascal's Triangle (Python, Go)
I tried LeetCode every day 125. Valid Palindrome (Python, Go)
I tried LeetCode every day 155. Min Stack (Python, Go)
I tried LeetCode every day 9. Palindrome Number (Python, Go)
I tried LeetCode every day 1. Two Sum (Python, Go)
I tried LeetCode every day 141. Linked List Cycle (Python, Go)
I tried LeetCode every day 13. Roman to Integer (Python, Go)
I tried LeetCode every day 110. Balanced Binary Tree (Python, Go)
I tried LeetCode every day 14.Longest Common Prefix (Python, Go)
I tried LeetCode every day 119. Pascal's Triangle II (Python, Go)
I tried LeetCode every day 168. Excel Sheet Column Title (Python, Go)
I tried LeetCode every day 111. Minimum Depth of Binary Tree (Python, Go)
I tried LeetCode every day 160. Intersection of Two Linked Lists (Python, Go)
Let Code Day48 Starting from Zero "26. Remove Duplicates from Sorted Array"
I tried LeetCode every day 121 Best Time to Buy and Sell Stock (Python, Go)
I tried LeetCode every day 122. Best Time to Buy and Sell Stock II (Python, Go)
Let Code Day 62 "83. Remove Duplicates from Sorted List"
I tried Grumpy (Go running Python).
I tried using UnityCloudBuild API from Python
I tried hitting the Qiita API from go
I tried Python! ] I graduated today from "What is Python! Python!"!
I tried debugging from Python via System Console
I tried running faiss with python, Go, Rust
I tried running python etc. from a bat file
I tried Python> autopep8
I tried Python> decorator
I tried to create API list.csv in Python from swagger.yaml
I tried using the Python library from Ruby with PyCall
I tried sending an email from Amazon SES with Python
I tried face recognition from the video (OpenCV: python version)
I tried changing the python script from 2.7.11 to 3.6.0 on windows10
I tried fp-growth with python
I tried scraping with Python
I tried Python C extension
[Python] I tried using OpenPose
I tried gRPC with Python
I tried scraping with python
Let Code Day86 Starting from Zero "33. Search in Rotated Sorted Array"
How to remove duplicates from a Python list while preserving order.