java - 重新排序数组，使 n 跟随 m

Question

我被要求重新排序一个数组，以便 n 跟随 m 的每个实例。我知道数组中 n 和 m 的数量相等。例如，如果每 3 后面跟着 4

[3,2,2,4] = [3,4,2,2]
[1,3,1,4,4,3,1] = [1,3,4,1,1,3,4]

我已经成功地解决了这个问题的大多数情况，除了上面示例中的一些情况外，第二个示例除了最后三个示例之外都有效。我编写代码的方式是搜索其余示例另外 4 个数组，但它出现在最后 3 个之前。下面是我的代码，

public static int[] reOrder(int[] arr) {
    int temp;

    for(int i = 0; i < arr.length; i++) {
        if(arr[i] == 3) {
            for(int j = i; j < arr.length; j++) {
                if(arr[j] == 4) {
                    temp = arr[i+1];
                    arr[i+1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }
    return arr;
}

Answer 1

您应该对 3 和 4 使用单独的指针，将 4 的最右边位置保留在内存中，因此代码应如下所示:

public static int[] reOrder(int[] arr) {
    int temp;
    for(int i = 0, j = 0; i < arr.length; i++) {
        if(arr[i] == 3 && i != arr.length - 1 && arr[i+1] != 4) { // we need to do it only if successor isn't 4, and position isn't last
            while (j < arr.length && arr[j] != 4 || (j > 0 && arr[j-1] == 3)) { //searching for first unused '4' in array
                j++;
            }
            if (arr[j] == 4) {
                temp = arr[i+1];
                arr[i+1] = arr[j];
                arr[j] = temp;
                j++;
            }
        }
    }
    return arr;
}