This is the 18th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

📢 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 51 days of continuous clocking of force button algorithm 🎈!
🚀 Algorithm 🚀

🌲 Move zero

Given an array nums, write a function to move all zeros to the end of the array while preserving the relative order of the non-zero elements

Example:

Input:0.1.0.3.12] output: [1.3.12.0.0]
Copy the code
Must operate on the original array, cannot copy additional arrays. Minimize the number of operations.Copy the code

🌻C# method: sort

If the current position of the array is not 0, the current value is assigned to the array [index], and the index increments by 1

If the current position is not equal to the position of the index (I can only be greater than or equal to index), then the current position is assigned to 0,

This is done to change the value following the array to 0

Code:

public class Solution {
    public void MoveZeroes(int[] nums) {
        int index =0;
        for(int i=0; i<nums.Length; i++){if(nums[i]! =0){
                nums[index] = nums[i];
                if(i! =index){ nums[i]=0; } index++; }}}}Copy the code

The execution result

By execution time:152Ms, in all C# beat 98.73% of users in submissionMemory consumption:51.5MB, in all CBeat 5.06% of users in # submission
Copy the code

🌻Java method: double pointer

The left pointer points to the tail of the currently processed sequence, and the right pointer points to the head of the sequence to be processed.

The right pointer moves to the right continuously. Each time the right pointer points to a non-zero number, the corresponding numbers of the left and right Pointers are switched, and the left pointer moves to the right at the same time.

Note the following properties:

The left side of the left pointer is non-zero; Zero to the left of the right pointer as far as the left pointer.Copy the code

Therefore, each swap swaps the zeros of the left pointer with the non-zero numbers of the right pointer, and the relative order of the non-zero numbers does not change.

Code:

class Solution {
    public void moveZeroes(int[] nums) {
        int n = nums.length, left = 0, right = 0;
        while (right < n) {
            if(nums[right] ! =0) { swap(nums, left, right); left++; } right++; }}public void swap(int[] nums, int left, int right) {
        inttemp = nums[left]; nums[left] = nums[right]; nums[right] = temp; }}Copy the code

The execution result

By execution time:2Ms, beat out all Java commits21.64% user memory consumption:39.9MB, beat out all Java commits5.01% of the userCopy the code

Complexity analysis

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

Java method two: hash table

We can directly query each number to see if it is present in the array to find the missing number. If a hash table is used, each query operation is constant time.

We insert all the numbers in the array into a set so that the time complexity of each query is O(1)

code

class Solution {
    public int missingNumber(int[] nums) {
        Set<Integer> numSet = new HashSet<Integer>();
        for (int num : nums) numSet.add(num);

        int expectedNumCount = nums.length + 1;
        for (int number = 0; number < expectedNumCount; number++) {
            if(! numSet.contains(number)) {returnnumber; }}return - 1; }}Copy the code

The execution result

By execution time:5Ms, beat out all Java commits33.30% user memory consumption:38.9MB, beat out all Java commits26.29% of the userCopy the code

Complexity analysis

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

💬 summary

  • Today is the fifty-first day of 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!

🚀 past quality articles to share

  • ❤ ️ Unity based to zero entry | the Unity game engine from 0 to 1 system study route suggest collection 】 【 comprehensive summary -!
  • 🧡 Spend a day making a high quality aircraft war game with over 10,000 word Unity complete tutorial! Beautiful school sister saw the call 666!
  • 💛 recall childhood and small partners played together the classic game [bomb people small game] production process + analysis
  • 💚 overnight a night to make a similar CS first person shooting game Demo! Turns out making games isn’t so hard
  • 🤍 blast liver a whole weekend to write a similar royal war real-time combat game Demo! More than 20,000 words game production process + analysis!
  • 💙 a similar “dinosaur kombat” horizontal version of the arcade fighting game how to make? | to learn together The way the source code suggest collect learning 】 【 code text is not easy,
  • 💜 super practical skills | 】 to improve writing quality and speed will learn skills: Typora figure bed configuration details