CODEWITHSUNDEEP
javaarraysruntime
dummy
dummy

Reputation: 127

how decrease runtime of arrays

I have solved the problem but I want to decrease its runtime. So is there any way to do this task? Task: Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

My solution:

public class Solution {
    public void moveZeroes(int[] nums) {
        int [] nums1=new int[nums.length];
        int k=-1;
        for(int i=0;i<nums.length;i++){
            if(nums[i]!=0){
                k++;
                nums1[k]=nums[i];
            }}
            for(int i=0;i<nums1.length;i++){
                 nums[i]=nums1[i];

            }
    }
}

Upvotes: 1

Views: 85

Answers (2)

havakok
havakok

Reputation: 1247

try this one:

public class Solution {
    public void moveZeroes(int[] nums) {
        int [] indexes=new int[nums.length];
        int k=0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]!=0){
                indexes[k]==i;
                k++;
            }
        }

        for(int i=0;i<nums.length;i++){
            if(i<k)
                nums[i]=nums[indexes[i]];
            else
                nums[i]=0;
        }
    }
}

i have first created a "mask" of all indexes not containing '0'(go over the array once O(N)). then you simply create the new array (go over all the array once O(N)). thus the complexity will be O(N).

Upvotes: 1

Tunaki
Tunaki

Reputation: 137194

You could take advantage of the fact that a primitive array of int will be created to all 0's by default. As such, you just need to create a result array having the same length of the original array and copy into it the non-zero element from the source array:

int[] result = new int[array.length];
int k = 0;
for (int v : array) {
    if (v != 0) {
        result[k++] = v;
    }
}

I've realized a JMH benchmark of your solution and this one on an array initialized with 100 millions random ints between -10 and 10. The results are (Windows 10, JDK 1.8.0_66, i5-3230M CPU @ 2.60 GHz):

Benchmark                 Mode  Cnt    Score    Error  Units
StreamTest.alternative    avgt   30  208,094 ± 29,928  ms/op
StreamTest.shiftSolution  avgt   30  250,888 ± 26,086  ms/op

which shows that this solution is indeed a bit faster (208 ms vs 251 ms).

Benchmark code for completeness:

import java.util.Random;
import java.util.concurrent.TimeUnit;

import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Fork;
import org.openjdk.jmh.annotations.Measurement;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Warmup;

@Warmup(iterations = 5, time = 1000, timeUnit = TimeUnit.NANOSECONDS)
@Measurement(iterations = 10, time = 1000, timeUnit = TimeUnit.NANOSECONDS)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@Fork(3)
@State(Scope.Benchmark)
public class StreamTest {

    private static final int[] ARRAY = new Random().ints(100000000, -10, 10).toArray();

    @Benchmark
    public int[] shiftSolution() {
        int[] nums1 = new int[ARRAY.length];
        int k = -1;
        for (int i = 0; i < ARRAY.length; i++) {
            if (ARRAY[i] != 0) {
                k++;
                nums1[k] = ARRAY[i];
            }
        }
        for (int i = 0; i < nums1.length; i++) {
            ARRAY[i] = nums1[i];

        }
        return nums1;
    }

    @Benchmark
    public int[] alternative() {
        int[] result = new int[ARRAY.length];
        int k = 0;
        for (int v : ARRAY) {
            if (v != 0) {
                result[k++] = v;
            }
        }
        return result;
    }

}

Upvotes: 2

Related Questions