java - 需要帮助解决 hackerrank 挑战

Question

我正在尝试解决 hackerrank 中的“Almost Sorted”挑战，问题是:

给定一个包含元素的数组，您能否仅使用以下操作之一按升序对该数组进行排序？

交换两个元素。 反转一个子段。

输入格式 第一行包含一个整数，表示数组的大小。

下一行包含由空格分隔的整数。

示例输入#1

2
4 2

示例输出 #1

是的
交换 1 2

示例输入#2

3

3 1 2

示例输出 #2

没有

示例输入 #3

6

1 5 4 3 2 6

示例输出 #3

是的

反转 2 5

我试图解决这个挑战，我的代码可以正常工作，但对于大数组来说它似乎变慢了。

恳请您帮助我为上述问题找到更好的解决方案。

下面是我的代码:

import java.util.*;

public class Solution
{
    private static int[] arr;

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();

        arr = new int[N];

        for (int i = 0; i < N; i++)
        {
            arr[i] = in.nextInt();
        }

        if (IsSorted(arr))
        {
            System.out.println("yes");
            return;
        }

        if(CheckSingleSwap(arr))
            return;

        if(CheckSingleReverse(arr))
            return;

        System.out.println("no");
    }

    private static boolean CheckSingleReverse(int[] arr)
    {
        int length = arr.length;
        int limit = length - 2;
        int current = 1;

        List<Integer> indexes = new ArrayList<Integer>();

        while (current < limit)
        {
            for (int i = 0; i < length; i++)
            {
                int temp = current + i;
                for (int j = i; j <= temp && temp < length; j++)
                {
                    indexes.add(j);
                }

                if (IsSorted(ReverseArrayPart(arr, indexes)))
                {
                    System.out.println("yes");
                    System.out.println("reverse " + (indexes.get(0) + 1) + " " + (indexes.get(indexes.size() - 1) + 1));

                    return true;
                }
                indexes.clear();
            }

            current++;
        }

        return false;
    }

    private static int[] ReverseArrayPart(int[] arr, List<Integer> indexes)
    {
        int[] result = new int[arr.length];
        int[] arrayPart = new int[indexes.size()];
        int j = 0;

        for (int i = 0; i < arr.length; i++)
        {
                if (indexes.contains(i))
                {
                    arrayPart[j] = arr[i];
                    j++;
                }

            result[i] = arr[i];
        }

        for(int i = 0; i < arrayPart.length / 2; i++)
        {
            int temp = arrayPart[i];
            arrayPart[i] = arrayPart[arrayPart.length - i - 1];
            arrayPart[arrayPart.length - i - 1] = temp;
        }

        j = 0;
        for (int i = 0; i < result.length; i++)
        {
                if (indexes.contains(i))
                {
                    result[i] = arrayPart[j];
                    j++;
                }
        }

        return result;
    }

    private static boolean CheckSingleSwap(int[] arr)
    {
        int count = 0;
        int[] B = Arrays.copyOf(arr, arr.length);
        Arrays.sort(B);
        List<Integer> indexes = new ArrayList<Integer>();

        for(int i = 0; i < arr.length; i++)
        {
            if(arr[i] != B[i])
            {
                count++;
                indexes.add(i+1);
            }
        }

        if(count > 2)
            return false;

        System.out.println("yes");
        System.out.println("swap " + indexes.get(0) + " " + indexes.get(1));

        return true;
    }

    private static boolean IsSorted(int[] arr)
    {
        int length = arr.length;

        for (int i = 0; i < length - 1; i++)
        {
            if (arr[i] > arr[i + 1])
            {
                return false;
            }
        }

        return true;
    }
}

Answer 1

对于下面的代码，传入A作为原始数组，B作为排序后的数组。

---

CheckSingleSwap:

不是将索引添加到另一个列表，而是存储您遇到的第一个交换，然后继续；如果找到相应的其他交换，则将其存储并记录发现；如果您找到一个不同的交换，则以 false 退出。最后，如果您记录了发现，请打印相应的索引。

private static boolean CheckSingleSwap(int[] A, int[] B)
{
    int L = A.length;
    int firstSwap = -1, secondSwap = -1;
    for(int i = 0; i < L; i++)
    {
        if(A[i] != B[i])
        {
            if (firstSwap == -1)
                firstSwap = i;
            else if (secondSwap == -1 && A[i] == B[firstSwap] && A[firstSwap] == B[i])
                secondSwap = i;
            else
                return false;
        }
    }
    if (firstSwap != -1 && secondSwap != -1)
    {
        System.out.println("yes");
        System.out.println("swap " + (firstSwap + 1) + " " + (secondSwap + 1));
        return true;
    }
    System.out.println("array is already sorted!");
    return false; // or whatever you decide to do; maybe even an exception or enumerated type
}

---

CheckSingleReverse:

您在这里做的方式太多了!您似乎在强制执行每一种可能的情况(乍一看)。

您可以做的是找到所有数字都不同的区域。如果有超过 两个 个，或者两个被多个 元素分隔，则立即返回 false。

上面“不止一个”的原因是奇数长度区域 - 中间 元素将是相同的。如果找到这样的两个区域，则将它们视为一个区域。然后你就可以继续查找该区域是否反转了。

private static boolean CheckSingleReverse(int[] A, int[] B)
{
    // find region
    int L = A.length;
    int diffStart = -1, diffEnd = -1; boolean mid = false, found = false;
    for (int i = 0; i < L; i++)
    {
        if (A[i] != B[i])
        {
            if (found)
            {
                if (i - diffEnd == 2 && !mid)
                {
                    mid = true;
                    found = false;
                    diffEnd = -1;
                }
                else
                    return false;
            }
            else if (diffStart == -1)
                diffStart = i;
        }
        else 
        if (diffStart != -1 && diffEnd == -1)
        {
            found = true;
            diffEnd = i - 1;
        }
    }
    if (diffEnd == -1)
    {
        if (A[L - 1] != B[L - 1])
            diffEnd = L - 1;
        else if (!found)
        {
            System.out.println("array is already sorted!");
            return false;
        }
    }

    // find out if it's reversed
    int count = (diffEnd - diffStart + 1) / 2;
    for (int i = 0; i < count; i++)
    {
        int oneEnd = diffStart + i, otherEnd = diffEnd - i;
        if (!(A[oneEnd] == B[otherEnd] && A[otherEnd] == B[oneEnd]))
            return false;
    }
    System.out.println("yes");
    System.out.println("reverse " + (diffStart + 1) + " " + (diffEnd + 1));
    return true;   
}

---

为了让您了解性能提升，在 ideone.com 上，数组长度为 150，CheckSingleReverse 的原始实现花费了 1.83 秒，而新的只用了 0.1 秒。长度为 250，原来的实际上超过了计算时间限制(5 秒)，而新的仍然只用了 0.12 秒。

由此看来，您的实现似乎需要指数时间，而我的是线性时间(忽略排序)。

有趣的是，对于 3 百万 的数组大小，我仍然得到大约 0.26 秒(ideone 的执行时间也有一点波动，可能是由于需求)