Java 算法 : Segregate Odd Even Numbers (time-space complexity)

Question

我正在编写一个方法来隔离整数数组，以便所有偶数整数都在数组中的所有奇数整数之前。它必须在数组 O(n) 的大小上花费线性时间，并且只需要恒定数量的额外空间就地运行。

输入:{2, 4, 7, 6, 1, 3, 5, 4}
输出:2, 4, 6, 4, 7, 1, 3, 5

输入:{5, 12, 3, 21, 8, 7, 19, 102, 201}
输出:12、8、102、5、3、21、7、19、201

这些是我的解决方案:

private static void segregateArray1(final int[] arr) {
    if (arr != null) {
        int leftIdx = 0;
        int rightIdx = arr.length - 1;

        while (leftIdx < rightIdx) {
            if (arr[leftIdx] % 2 != 0 && arr[rightIdx] % 2 == 0) {
                // swap immediately
                int temp = arr[leftIdx];
                arr[leftIdx] = arr[rightIdx];
                arr[rightIdx] = temp;
                leftIdx++;
                rightIdx--;
            } else {
                if (arr[leftIdx] % 2 == 0) {
                    leftIdx++;
                }
                if (arr[rightIdx] % 2 == 1) {
                    rightIdx--;
                }
            }
        }
    }
}

方法一耗时O(n)，不占用额外空间。但是，它不维持秩序。

private static int[] segregateArray2(final int[] arr) {
    List<Integer> evenArr = new ArrayList<Integer>();
    List<Integer> oddArr = new ArrayList<Integer>();

    for (int i : arr) {
        if (i % 2 == 0) {
            evenArr.add(i);
        } else {
            oddArr.add(i);
        }
    }
    evenArr.addAll(oddArr);

    return ArrayUtils.toPrimitive(evenArr.toArray(new Integer[0]));
}

方法二创建ArrayList。我不确定这是否也是 O(n)。

测试:

public static void main(String[] args) {
    int[] arr = {2, 4, 7, 6, 1, 3, 5, 4};
    segregateArray1(arr);
    System.out.println(Arrays.toString(arr));

    int[] arr = {2, 4, 7, 6, 1, 3, 5, 4};
    // creates another array segragatedArr!
    int[] segragatedArr = segregateArray2(arr);
    System.out.println(Arrays.toString(segragatedArr));
}

我不确定是否有满足时空复杂度(O(n) 和空间限制)的更简洁的解决方案/简单性。

Answer 1

执行此操作并保持相同的时间复杂度以及输出数组的大小与输入数组的大小相同的最简单方法是对每个值进行模数检查，如果它是正数则放置到数组的前面，如果是负数则返回数组的后面。请记住，您将需要两个变量来了解正数和负数的下一个可用位置