LeetCode-26. Delete duplicates in ordered arrays (day7)

Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit series activities – click on the task to see the details of the activities.

One, foreword

👨🎓 Author: Bug Bacteria

✏️ blog: CSDN, Nuggets, etc

💌 public account: Magic House of the Circle of the Apes

🚫 special statement: original is not easy, reprint please attach the original source link and this article statement, thank you for your cooperation.

🙏 Copyright notice: part of the text or pictures in the article may come from the Internet or Baidu Encyclopedia, if there is infringement, please contact bug bacteria processing.

Hello, little friends, I am bug bacteria 👀. Gold three silver four, brush the month again. So whether you’re looking for a career change or a career change, get your act together and do the right thing 👣. So, quickly follow the pace of bug bacteria roll up ⏰, become strong from this moment ➕🧈.

In the process of reviewing articles, if you think the articles are helpful to you at all, please don’t be too mean with your likes and bravely light up the articles 👍. Your likes (collect ⭐️+ pay attention to 👨 port + message board) are the best encouragement and support for bugs on my creation path. Time does not abandon 🏃🏻♀️, nuggets stop 💕, cheer up 🏻

Ii. Title Description:

Topic:

Give you an array nums in ascending order, ask you to delete duplicate elements in place, make each element appear only once, return the new length of deleted array. The relative order of elements should be consistent.

Because you cannot change the length of an array in some languages, you must place the result in the first part of the array NUMS.

More formally, if there are k elements after removing duplicates, then the first K elements of NUMS should hold the final result. Returns k after inserting the final result into the first k positions of numS.

Instead of using extra space, you have to modify the input array in place and do it with O(1) extra space.

The system will test your problem solving with the following code:

int[] nums = [...] ; ExpectedNums = [...] ; Int k = removeDuplicates(nums); // Call assert k == ExpectedNums.length; for (int i = 0; i < k; i++) { assert nums[i] == expectedNums[i]; }Copy the code

If all assertions pass, your problem is passed.

See the following example for details:

Example 1:

Input: nums = [1,1,2] Output: 2, nums = [1,2,_] Explanation: The function should return a new length of 2, and the first two elements of the original nums array are changed to 1,2. You don't need to worry about the element after the new length in the array.Copy the code

Example 2:

Input: nums = [0,0,1,1,1,2,2,3,3,4] Output: 5, nums = [0,1,2, 2,3,4] Explanation: The function should return a new length of 5, and the first five elements of the original array NUMs are modified to 0,1,2,3,4. You don't need to worry about the element after the new length in the array.Copy the code

Tip:

0 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
numsThey are arranged in ascending order

LeetCode ⭐⭐

Iii. Analysis of Ideas:

Get this question, a look at such a long topic, suddenly stunned, but careful analysis of the meaning of the question can be:

An array is ordered, so duplicate elements must be contiguous.
Asking for a duplicate element to be removed essentially moves the non-duplicate element to the left of the array.

So the implementation method is very simple: directly use the fast and slow Pointers for traversal replacement, and finally output the slow pointer low is the problem. Specific approach: define two Pointers, one in the front as low, one in the post as fast.

The algorithm flow is as follows: Compare whether the elements at low and fast positions are equal.

If they are equal, fast moves back by 1 bit.
If they are not equal, copy the elements of the fast position to the low+1 position, low moves back by 1, and fast moves back by 1
Repeat the process until FAST equals the array length. Return low + 1, which is the length of the new array.

Iv. Algorithm implementation:

Double pointer method _AC code

The specific algorithm code is as follows:

Class Solution {public int duplicates (int[] nums) {// Start from 0 int slow = 0; Int fast = 1; for (; fast < nums.length; ) {// If not equal, the slow pointer moves forward one bit. if (nums[slow] ! = nums[fast]) {// if (slow + 1) nums[fast] = nums[fast]; // slow moves right by 1 slow++; } // move the fast pointer right one bit fast++; } // Return (slow+1) return slow+1; }}Copy the code

V. Summary:

The screenshot of the two-pointer leetcode submission result is as follows:

Complexity analysis:

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

You should actually notice that they don’t want to use extra space, and they have to do it in place, and they have to do it in O(1) space. So it’s actually pretty easy to do, again, an ascending array, just to shift the same value with a fast or slow pointer and if there’s no constraint, it’s actually a lot easier, either by iterating through and adding a new array or by adding a new array with a map.

If you have any better ideas or ideas, please let me know in the comments section. We can learn from each other and grow faster.

Well, that’s all for this episode and I’ll see you next time.

Six, the previous recommendation:

Leetcode -1. Sum of two numbers
Leetcode – 9. Palindrome
Leetcode -13. Roman numeral to integer
Leetcode -14. The longest public prefix
Leetcode -20. Valid parentheses
Leetcode -21. Merge two ordered lists

. .

Vii. End of article:

If you want to learn more, check out bug Bug’s LeetCode Problem of the Day column! Take you to brush together. One person may feel very tired and difficult to persist in brushing, but a group of people will think it is a meaningful thing to brush, urge and encourage each other, and become stronger together.

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

☘️ Be who you want to be, there is no time limit, you can start whenever you want,

🍀 You can change from now on, you can also stay the same, this thing, there are no rules to speak of, you can live the most wonderful yourself.