如何减少数组的运行时间
how decrease runtime of arrays
我已经解决了这个问题,但我想减少它的运行时间。那么有什么办法可以完成这个任务吗?
任务:给定一个数组 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];
}
}
}
您可以利用 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;
}
}
试试这个:
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)。
我已经解决了这个问题,但我想减少它的运行时间。那么有什么办法可以完成这个任务吗? 任务:给定一个数组 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];
}
}
}
您可以利用 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;
}
}
试试这个:
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)。