java - 在 O(n) 时间和 O(1) 空间内将所有 x 元素插入数组末尾

Question

我正在尝试解决算法任务，但不幸的是无法为它想出一些最佳方法。我们得到一个数组，任务是移动数组末尾的所有元素 x。例如
输入[1,2,3,4,1,2,3,4,5,6,5]
输出 [2, 3, 4, 2, 3, 4, 5, 6, 5, 1, 1]

Answer 1

你可以这样实现

import java.util.Arrays;

public class Rearrange
{

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

    private static void reArrange(int[] arr, int x) {
        int index = 0;
        for (int current : arr)
            if (current != x)
                arr[index++] = current;
        Arrays.fill(arr, index, arr.length, x);
    }

}

输出

[2, 3, 4, 2, 3, 4, 5, 6, 5, 1, 1]