Java中从数组中删除负数

Question

我的目标是从Java数组中删除所有负数。

我已经编写了以下代码。我该如何改进代码的复杂度，或者是否有更好的算法？

public static void main(String[] args) {
    int[] array = { 1, -3, 4, -9, 3, 4, 70, -10, 0, 7 };
    System.out.println(Arrays.toString(removeNegativeNumbers(array)));
}

public static int[] removeNegativeNumbers(int[] num) {
    List<Integer> list = new ArrayList<>();
    for (int n : num) {
        if (n >= 0) {
            list.add(n);
        }
    }
    int[] result = new int[list.size()];
    for (int i = 0; i < result.length; i++) {
        result[i] = list.get(i).intValue();
    }
    return result;
}

- user7117165

Answer 1

Java 8 流是怎样的呢？

Arrays.stream(num).filter(s -> s >= 0).toArray();

- user6904265

---

最佳解决方案，但0不是负数。 - Esben Skov Pedersen

这确实实现了原帖中所要求的“提高代码复杂度”。 - Hulk

97%的时间，这是你应该使用的东西。 - jk.

支持简洁的Java语法。但这个答案并没有像提问者要求的那样表明任何关于算法的东西，它只是展示了Java具有多么强大的API可以实现一行代码。 - Kaidul

这将适用于 int[]、long[]、double[] 和任何 Object[]，但不适用于 byte[]、short[]、char[] 或 float[]，因为这些类型没有 Arrays.stream 方法。 - Boann

Answer 2

这里有一个线性的O(n)算法，空间复杂度为常数级别（忽略了输出数组需要的空间）。当元素是非负数时，将该元素复制并同时推进输出数组和输入数组搜索指针。当元素为负数时，只推进输入数组的搜索指针(indx)，避免复制到输出数组中。

public static int[] removeNegativeNumbers(int[] num) {
    int[] output = new int[num.length];
    int k = 0;
    for(int i = 0; i < num.length; i++) {
       if(num[i] >= 0) {
           output[k++] = num[i];
       }
    }
    return Arrays.copyOfRange(output, 0, k);
}

高效利用空间的解决方案

您可以通过将输入数组转换为像插入排序一样保存输出的方式，使算法实现原地计算，以避免输出数组的空间开销。

public static int removeNegativeNumbers(int[] num) {
    int k = 0;
    for(int i = 0; i < num.length; i++) {
       if(num[i] >= 0) {
           num[k++] = num[i];
       }
    }
    // Now input array is holding the output data
    // Return the length of output array
    return k;
}

// Usage: int newLen = removeNegativeNumbers(array);

这被称为双指针技术，非常简单但有用，可以解决许多经典难题，如数组去重、合并两个已排序的数组、两个已排序的数组的交集等。

- Kaidul

---

空间复杂度为O(n)，不能称其为常数。 - आनंद

@AnandTyagi 是的，我是通过复制输入数组来返回的..谢谢指出。现在请检查更新。 - Kaidul

请注意，第二个代码示例是“原地”解决方案 - 第一个解决方案使用辅助数组。 - Thomas

+1 有几个原因。首先，有两种实现方式：一种是直接实现，另一种是更高效、更“棘手”的实现方式。其次，数组大小事先指定（与输入数组大小相同）。在问题中使用了一个ArrayList，它会根据需要动态调整大小，并且API隐藏了数据结构可以扩展到远远超出此算法需求的事实，因此隐藏了潜在的重大低效性。 - Christopher Schultz

Answer 3

我认为在效率方面，我们无法比@kaidul-islam的答案（以及@user6904265的简洁性）更好。

我只是添加了一个解决方案，在非常特定的场景中应该有一定的价值，其中负数很少出现且数组非常大。

基本思想是推迟实际复制，直到找到负值，然后使用System.arraycopy进行复制。如果没有找到负值，则返回源数组。

import java.util.*;

public class NotNegativeTest {

    public static void main(String[] args) {
         int[] array = { 1, -3, 4, -9, 3, 4, 70, -10, 0, 7 }; 
         System.out.println(Arrays.toString(removeNegativeNumbers(array))); 
    } 

    public static int[] removeNegativeNumbers(int[] num) {
         int[] output = new int[num.length];
         int k = 0;
         int i = 0; 
         int last=-1;
         int howmany=0;

         while(i < num.length) {
             if(num[i] < 0) {
                howmany=i-last-1;
                switch(howmany) {
                    case 0: break;
                    case 1: 
                            output[k]=num[last+1];
                            k++;
                            break;
                    default:        
                            System.arraycopy(num, last+1,  output, k, howmany);
                            k+=howmany;
                }
                last=i;
             } 
             i++;
         } 
         if (last>=0) {
              if(last!=i-1) {
                howmany=i-last-1;  
                System.arraycopy(num, last+1,  output, k, howmany);
                k+=howmany;
            }
        } else {
            return num;
        }

         return Arrays.copyOfRange(output, 0, k);
     }

}

我已经找到时间编写了一个JMH微基准测试。

我使用了以下配置：

Options opts = new OptionsBuilder()
  .include(MyBenchmark.class.getSimpleName())
  .mode(Mode.AverageTime)
  .warmupIterations(1)
  .warmupTime(TimeValue.seconds(5))
  .measurementIterations(10)
  .measurementTime(TimeValue.seconds(5))
  .jvmArgs("-server")
  .forks(1)
  .build();
new Runner(opts).run();

（免责声明：这是我第一次进行JMH测试，如果有人有建议，我很乐意更改并更新结果）

以下是测试结果：

# Run complete. Total time: 00:02:54

Benchmark                             Mode  Cnt  Score   Error  Units
MyBenchmark.testMethodUser6904265     avgt   10  0,201 ± 0,040   s/op
MyBenchmark.testMethodInsac           avgt   10  0,093 ± 0,022   s/op
MyBenchmark.testMethodKaidul          avgt   10  0,124 ± 0,029   s/op

现在，在为我欢呼之前，请看一下测试有多么偏颇：

 int[] array = new int[10000000];
 array[0]=-5;
 array[10000]=-3;
 array[40000]=-3;
 array[8000000]=-3;

 int[] answer=NotNegativeTest.removeNegativeNumbers(array);

所以需要注意的是，我的方法并不是赢了（测试是为了让我的方法赢得胜利:-)，而是即使在这种极端情况下，通用的kaidul-islam方法与我的方法非常接近。

更新：这里是我编写的jmh基准测试链接，您可以验证更现实的情况（如果有人发现我设置测试的问题，请告诉我）。还有一个依赖于Trove的测试，我在另一个答案中做了说明。

- Insac

---

+1 表示展示三种方法相对于基准测试的性能指标。是的，在这种情况下，您的方法肯定会获胜。如果我们事先知道情景，那么这是可以做到的。然而，如果空间是一个问题，我们仍然可以使您的方法原地进行。 - Kaidul

Answer 4

以下方法在单次迭代中完成：

在原始数组上保持两个索引：src和dst，它们都初始化为0。

当数字是正数时，从num[src]复制到num[dst]并同时增加两个索引。

当数字是负数时，只需增加src的值。

将具有dst作为其新大小的原始数组返回。

public static int removeNegativeNumbers(int[] num) {
  int dst=0;
  for (int src=0 ; src<num.length ; ++src)
    if (num[src]>=0)
      num[dst++] = num[src];
  return dst;
}

- Shloim

---

这绝对是最快的方式。 - Boann

它也是具有破坏性的，这可能是可以接受的，也可能不可以。 - Surt

Answer 5

请按照以下代码实现（Java 8）

int test[] = new int[] { 15, -40, -35, 45, -15 };
    // here we can take the test array in to stream and filter with condition (>=0).
    int[] positives = Arrays.stream(test).filter(x -> x >= 0).toArray();

    System.out.println("Here is the positive array elements");

    for (int i : positives) {
        System.out.print(i + "\t");
    }

- Lova Chittumuri

Answer 6

由于您必须查看每个单独的元素以确定它是否小于0，因此运行时间必须至少为O（n）。由于存储输入所需的空间为O（n），因此空间至少为O（n）。您的解决方案在O（n）时间内运行，并具有O（n）复杂度，因此没有解决方案可以比您的解决方案具有更好的空间或运行时复杂度 然而，如果我们假设数组已排序，则可以获得更好的结果。然后，我们对0进行二进制搜索。如果我们有一种返回子数组的方法，并且时间是恒定的（例如，在C中使用指针幻术，或者通过返回要读取的起始索引来实现），则算法的时间将为O（log n）。

- Ryan Amos

---

如果你只考虑抽象的时间复杂度，那么你忽略了与问题中的 ArrayList<Integer> 相关的 Integer 装箱、编译器生成的类型转换和动态重新分配的开销。它仍然是摊销 O(n)，但在实践中它并不像它本来可以那样快。 - Boann

@Boann，是的，那是真的。如果您不想增加复杂性，有几种处理ArrayList和装箱的方法可以避免平摊O(n)。这些在其他答案中已经涵盖了。我主要想解决其他答案没有解决的问题：OP算法的复杂度无法改进。 - Ryan Amos

Answer 7

使用迭代器。

  Iterator<Integer> itr = objArray.iterator();
     while(itr.hasNext()) {
     Integer next = itr.next();
     if(next < 0) {
        itr.remove();
     }
  }

- MounyaSri

Answer 8

public static int[] removeNegativeNumbers(int[] num) {
    List<Integer> list = new ArrayList<>();
    for (int n : num) {
        if (n >= 0) {
            list.add(n);
        }
    }
    return list.toArray(new int[list.size()]);
}

- Mangu Singh Rajpurohit

---

这与问题中的代码有何不同？ - OneCricketeer

通过使用list.toArray在ArrayList上，他正在优化从列表到最终数组的步骤。幕后list.toArray（记住，list是一个ArrayList）正在使用System.arrayCopy。 - Insac

如果包含@Insacs评论中的解释，这个答案会更好。 - Hulk

无法编译。您不能调用toArray()在List<Integer>上获取int[]，只能获取一个可怕的Integer[]。从列表中获取int[]的唯一方法是手动创建和填充它，就像问题中的代码所做的那样。 - Boann

@Boann 你说得对，我之前没有注意到 :-(.. 不过，如果发帖者用一些实用的原始 int 列表（例如 Trove TIntArrayList）替换 List<Integer>，答案仍然是可挽救的。 - Insac