如何在交换算法中实现return

Question

我正在编写代码来实现交换，将偶数索引处的所有元素放置为小于或等于它们的邻居，并将奇数索引处的所有元素放置为大于或等于它们的邻居。我需要在重新排列方法的末尾有一个 return 语句，但由于没有 if else 语句，我有点不知所措。任何帮助将不胜感激！

public class Problem3 {

public static boolean rearrange(int[] A)
{
    /*
Input: an array, A, of n sorted integers (positive, negative, or 0) that 
A[0] <= A[1] <= A[2] <=…A[n-2] <= A[n-1]

Output: re-arrange elements in A such that: 
Element at even position (i.e., A[0], A[2]) are less than or equal to both of its neighbors
Element at odd position (i.e., A[1], A[3]) are greater than or equal to both of its neighbors

A[0] <= A[1] >= A[2] <= A[3] >= A[4] <= A[5]…

Design an algorithm that solves this problem in O(n) time.

     */
    for (int i=1; i<A.length-1;){
        swap(A,A[i],A[i+1]);
    }

}

public static void swap(int[] A, int i, int j){
    int temp = A[i];
    A[i] = A[i+1];
    A[i+1] = temp;
}

public static void main(String[] args) {

    int[] A = {13, 20, 45, 69, 78, 100, 127, 155};

    System.out.println("Before:");

    for(int i=0; i < A.length; i++){

        System.out.print(A[i]+" ");
    }

    rearrange(A);

    System.out.println("After:");

    for(int i=0; i < A.length; i++){

        System.out.print(A[i]+" ");
    }



}

}

Answer 1

在我看来，如果方法无法重新排列数组，您可以 return false。例如，如果违反了某些合同。在你的任务中，我看到了两个合同：

输入不应该是null
输入数组应该排序。

在这种情况下，您的方法可以如下所示：

public static boolean rearrange(int[] A) {
    if (A == null || !isSorted(A)) {
        return false;
     }

     .... rearranging algorithm here
     return true;
}

Answer 2

我认为使用循环来交换数组和额外的指针变量 J 是相当昂贵的，因为如果你使用循环那么它会将复杂度提高到 2N。

循环会像((N+1)+N)那样执行，也就是2N。

我相信用 recursion 投入资金将是有利的，下面我将分享我尝试递归的相同内容。然而 return 应该独立于碱基调用，验证可以在调用工作函数的实际逻辑之前自行完成。

public class Problem3 {

    /*
     * Input: an array, A, of n sorted integers (positive, negative, or 0) that
     * A[0] <= A[1] <= A[2] <=…A[n-2] <= A[n-1]
     * 
     * Output: re-arrange elements in A such that: Element at even position
     * (i.e., A[0], A[2]) are less than or equal to both of its neighbors
     * Element at odd position (i.e., A[1], A[3]) are greater than or equal to
     * both of its neighbors
     * 
     * A[0] <= A[1] >= A[2] <= A[3] >= A[4] <= A[5]…
     * 
     * Design an algorithm that solves this problem in O(n) time.
     * 
     */
    public static int[] swap(int[] A, int i) {
        if (i < A.length - 1) {
            int temp = A[i];
            A[i] = A[i + 1];
            A[i + 1] = temp;
            i = i + 1;
            swap(A, i);
        }
        return A;
    }

    public static void main(String[] args) {

        int[] A = { 13, 20, 45, 69, 78, 100, 127, 155 };

        System.out.println("Before:");

        for (int i : A) {

            System.out.print(i + " ");
        }

        System.out.println("\nAfter:");

        for (int i : swap(A, 0)) {

            System.out.print(i + " ");
        }

    }

}

如何在交换算法中实现return

How to implement return in swapping algorithm

java

algorithm

swap