如何减少数组的运行时间

Question

我已经解决了这个问题，但我想减少它的运行时间。那么有什么办法可以完成这个任务吗？任务：给定一个数组 nums，编写一个函数将所有 0 移动到它的末尾，同时保持非零元素的相对顺序。

例如，给定 nums = [0, 1, 0, 3, 12]，调用您的函数后，nums 应为 [1, 3, 12, 0, 0]。

我的解决方案：

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];

            }
    }
}

Answer 1

您可以利用 int 的原始数组默认创建为全 0 的事实。因此，您只需要创建一个与原始数组长度相同的结果数组，并将源数组中的 non-zero 元素复制到其中：

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

我已经实现了你的解决方案的 JMH 基准测试，这个是在一个数组上实现的，该数组用 -10 到 10 之间的 1 亿个随机整数初始化。结果是 (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

这表明此解决方案确实快了一点（208 毫秒对 251 毫秒）。

完整性基准代码：

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;
    }

}

Answer 2

试试这个：

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;
        }
    }
}

我首先创建了一个 "mask" 的所有不包含“0”的索引（遍历数组一次 O(N)）。然后你只需创建新数组（遍历所有数组一次 O(N)）。因此复杂度为 O(N)。

如何减少数组的运行时间

how decrease runtime of arrays

java

arrays

runtime