在 Java 中从数组中删除负数

algorithm java

2022-09-02 04:55:24

我的目标是从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;
}

答案 1

Java 8 流呢？

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

答案 2

如何提高代码的复杂性，或者是否有好的算法？

这是一个具有恒定空间的线性算法（忽略输出数组所需的空间）。当元素为非负数时，复制该元素并推进输出数组和输入数组导引头。当元素为负数时，仅推进输入数组搜索器（indx），并避免复制到输出数组。O(n)

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

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