Algorithm gymnastics 7

Move zeros to left

Description

An array of integer type is passed. Let's implement an algorithm that moves all elements equal to 0 to the left while maintaining the order of the other elements in the array. Let's take a look at the following integer array.

Screen Shot 2019-12-20 at 17.42.26.png

Moving all zero-equal elements to the left, the array looks like this: (Must keep the order of non-zero elements)

Screen Shot 2019-12-20 at 17.44.09.png

Solution

Runtime Complexity O(n) You need to find the 0 element in the array. Memory Complexity O(1) It can be implemented only with the array passed by using two pointers (iterators).

The main flow of the algorithm is

  1. Place the two markers read_index and write_index on the last element of the array. <img width = "593" alt = "Screen Shot 2019-12-20 at 17.57.38.png " src = "https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0" /405022/4eb6fef7-29d6-0684-1a39-91df7a6d3f80.png ">

  2. While read_index is 0 or greater

  3. If read_index points to "0", decrement only read_index. <img width = "594" alt = "Screen Shot 2019-12-20 at 17.58.40.png " src = "https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0" /405022/e6fc1c0e-cc76-b5b6-44f7-764ead2af83a.png "> Screen Shot 2019-12-20 at 17.59.16.png If read_index points to a non-zero value, write an element of read_index to write_index and decrement both write_index and read_index. <img width = "564" alt = "Screen Shot 2019-12-20 at 17.59.59.png " src = "https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0" /405022/6b20aea1-b27b-2a3d-344d-dee0eda0c1d4.png ">

  4. read_index becomes -1, exit the loop, and assign the elements of the array to 0 from the current write_index to 0. Screen Shot 2019-12-20 at 18.02.31.png Screen Shot 2019-12-20 at 18.03.14.png

  5. Completion Screen Shot 2019-12-20 at 18.03.32.png

Implementation

moveZeroToLeft.java


public class moveZerosToLeft {
    public void move_zeros_to_left_in_array(int[] A) {

        int readIndex = A.length - 1;
        int writeIndex = A.length -1;

        while (readIndex >= 0) {

            if (A[readIndex] != 0) {
                A[writeIndex] = A[readIndex];
                writeIndex--;
            }
            readIndex--;
        }

       while (writeIndex >= 0) {
           A[writeIndex] = 0;
           writeIndex--;
       }
    }
}

Mina.java


import java.util.Arrays;

public class Main {

    public static void main(String[] args) {
        // write your code here
        moveZerosToLeft algorithm = new moveZerosToLeft();

        int[] v = new int[]{1, 10, -1, 11, 5, 0, -7, 0, 25, -35};
        System.out.println("Original Array: " + Arrays.toString(v));
        algorithm.move_zeros_to_left_in_array(v);
        for (int item : v) {
            System.out.print(item + ", ");
        }
    }
}

Output Screen Shot 2019-12-20 at 18.06.27.png

Recommended Posts

Algorithm gymnastics 12
Algorithm gymnastics 10
Algorithm gymnastics 3
Algorithm gymnastics 9
Algorithm gymnastics 14
Algorithm gymnastics 7
Algorithm Gymnastics 15
Algorithm Gymnastics 16
Algorithm gymnastics 8
Algorithm Gymnastics 17
Algorithm Gymnastics 18
Algorithm gymnastics 11
Algorithm gymnastics 5
Algorithm gymnastics 4
Algorithm Gymnastics 24 Subsets
Algorithm Gymnastics 23 Merge Intervals
Algorithm Gymnastics 20 Remove Duplicates
Algorithm Gymnastics 21 LinkedList Cycle
Algorithm Gymnastics 24 Cyclic Sort
Algorithm Gymnastics 19 No-repeat Substring
Algorithm exercise 6
Algorithm Gymnastics 24 Reverse a Linked List
Python algorithm
Algorithm exercises 13
Algorithm Gymnastics 20 Pair with Target Sum
Algorithm Gymnastics 22 Squaring a Sorted Array
Algorithm Gymnastics 24 Middle of the Linked List
Python memorandum (algorithm)
Dictionary learning algorithm
String search algorithm