Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

📢 preface

🚀 Algorithm 🚀
  • 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
  • 🌲 tip: the programming languages used in this column are C# and Java
  • 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
  • 🌲 today is the force button algorithm continued to punch the card 13 days 🎈!
🚀 Algorithm 🚀

🌲 Example of original problem

Give you an ordered array nums, ask you to delete the repeated elements in place, so that each element appears only once, return the deleted array after the new length.

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

Description:

Why is the return value an integer, but the output answer is an array?

Note that the input array is passed “by reference,” which means that modifying the input array in a function is visible to the caller.

You can imagine the internal operation as follows:

// Nums is passed by reference. That is, do not make any copies of the arguments
int len = removeDuplicates(nums);

// 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
The sample1: Input: nums = [1.1.2] output:2, nums = [1.2The 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.Copy the code
The sample2: Input: nums = [0.0.1.1.1.2.2.3.3.4] output:5, nums = [0.1.2.3.4The 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

Tip:

  • 0 <= nums.length <= 3 * 104
  • -104 <= nums[i] <= 104
  • Nums are sorted in ascending order

🌻C# method 1: double pointer

Thinking analytical

An array is ordered, so two elements that repeat must be adjacent!

They also ask you to remove duplicate elements, which is essentially moving the non-duplicate elements to the left of the array

We take two Pointers, one preceded by p and one followed by Q

Algorithm flow:

  • To comparep 和 qWhether the elements of the position are equal.
  • If it’s equal,q Back one
  • If it is not equal, willqPosition the element top+1Position,pMove back one,q Move backward1 位
  • Repeat the process untilq Equals the length of the array.
  • returnp + 1Is the length of the new array.

Illustration:

Code:

public class Solution {
    public int RemoveDuplicates(int[] nums) {
        if(nums == null || nums.Length == 0) return 0;
    int p = 0;
    int q = 1;
    while(q < nums.Length){
        if(nums[p] ! = nums[q]){ nums[p +1] = nums[q];
            p++;
        }
        q++;
    }
    return p + 1; }}Copy the code

The execution result

By execution time:224Ms, in all C# beat 97.82% of users in submissionMemory consumption:33.3MB, in all C# beat 45.00% of users in submission
Copy the code

Complexity analysis

Time: O(n) Space: O(1)
Copy the code

🌻Java method 1: dual Pointers

Code:

class Solution {
 public int removeDuplicates(int[] nums) {
    if(nums == null || nums.length == 0) return 0;
    int p = 0;
    int q = 1;
    while(q < nums.length){
        if(nums[p] ! = nums[q]){ nums[p +1] = nums[q];
            p++;
        }
        q++;
    }
    return p + 1; }}Copy the code

The execution result

By execution time:1Ms, beat out all Java commits92.42% user memory consumption:39.8MB, beat out all Java commits66.60% of the userCopy the code

Complexity analysis

Time complexity: O(n) Space complexity: O(1)
Copy the code

💬 summary

  • Today is the thirteenth day of the buckle algorithm clocking!
  • The article USES theC# andJavaTwo programming languages to solve the problem
  • Some methods are also written by the god of reference force buckle, and they are also shared while learning, thanks again to the algorithm masters
  • That’s the end of today’s algorithm sharing, see you tomorrow!