Leetcode-27. Removing elements (day8)

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:

** Given an array nums and a value val, you need to remove all elements equal to val in place and return the new length of the array. Instead of using extra array space, you must only use O(1) extra space and modify the input array in place. The order of elements can be changed. You don’t need to worry about the element after the new length in the array.

You can imagine the internal operation as follows:

// Nums is passed by reference. Int len = removeElement(nums, val); // Modifying the input array in a function is visible to the caller. // Depending on the length returned by your function, it prints out all elements in the array within that length. for (int i = 0; i < len; i++) { print(nums[i]); }Copy the code

See the following example for details:

Example 1:

Input: nums = [3,2,2,3], val = 3 Output: 2, nums = [2,2] Explanation: The function should return a new length of 2, and the first two elements of nums are both 2. You don't need to worry about the element after the new length in the array. For example, the function returns a new length of 2, and nums = [2,2,3,3] or nums = [2,2,0,0] will also be considered the correct answer.Copy the code

Example 2:

Input: nums = [0,1,2,2,3,0,4,2], val = 2 Output: 5, nums = [0,1,4,0,3] Explanation: The function should return the new length 5, and the first five elements in nums are 0,1, 3,0,4. Notice that these five elements can be in any order. You don't need to worry about the element after the new length in the array.Copy the code

Tip:

0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

LeetCode ⭐⭐

Iii. Analysis of Ideas:

26. Delete duplicates from an ordered array. How do you do that?

Start by defining a variable index that points to the position to be inserted. Index = 0, then remove all elements equal to val to determine the following two directions when traversing any element nums[I] :

If the current elementnums[i]And removing elementsvalIf so, skip the element.
If the current elementnums[i]And removing elementsvalDifferent, that willnums[i]Put it at index and shift it to the rightindex++.
So index is the answer.

Iv. Algorithm implementation:

1. AC code

The specific algorithm code is as follows:

Class Solution {public int removeElement(int[] nums, int val) {// Int index = 0; for (int i = 0; i < nums.length; I++) {// equal will be skipped, not equal will be retained. if (nums[i] ! If (val) {// nums[index] = nums[I]; // right index++; } } return index ; }}Copy the code

V. Summary:

The screenshot of leetcode submission results is as follows:

Complexity analysis:

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

To solve this problem, there is only one thing to note. First, it is necessary to remove all elements equal to val in place, which is the basis for the implementation of the fast and slow pointer method.

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
Leetcode -26. Remove duplicates from ordered arrays

. .

Vii. End of article:

If you want to learn more, check out bug Bug’s LeetCode Problem of the Day column! With you brush together, each column is attached with a detailed solution, hand in hand with you to solve the problem.

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.

Finally send you two words, with you!

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

☘️ 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.