[HackerRank]幾乎完成的排序(Almost Sorted)

題目描述

給定一個擁有許多元素的整數陣列，您可以使用一次以下其中一種方式將它改變成遞增排序嗎？

原題網址

輸入格式

第一行為一個整數n，表示陣列的大小。n的範圍在2到100000之間(包含2和100000)。

接下來的一行為陣列的元素，使用空格分開。元素的值在0到1000000之間(包含0和1000000)，每個元素皆不相同。

輸出格式

如果陣列已經被排序，只需輸出「yes」就好。
如果您可以僅使用一個方式將其排序完成，要先輸出「yes」，接著根據您用的方式在接下來的一行繼續輸出。若您使用交換元素的方法，輸出「swap l r」，l為要左邊交換元素的位置，r為右邊交換元素的位置。若您使用反轉子陣列的方法，輸出「reverse l r」，l為子陣列最左邊元素的位置，r為子陣列最右邊元素的位置。若同時可以使用交換元素和反轉子陣列的方法，則使用交換元素的方法。

範例輸入1

範例輸出1

範例輸入2

範例輸出2

範例輸入3

範例輸出3

額外解釋

第一個範例中，您可以swap(1, 2)或是reverse(1, 2)來完成排序，所以只輸出交換元素的作法。
第二個範例中，無法使用一次交換元素或是反轉陣列的方式來完成排序。
第三個範例中，可以使用reverse(2, 5)來完成排序。

解題概念

為了解題方便，可將原始陣列的長度改成n+2，並且在新陣列的第一個元素和最後一個元素擺上邊界，就是比最小值還要更小的值和比最大值還要更大的值。在這題目中，輸入的陣列元素範圍在0到1000000之間(包含0和1000000)，所以設定新陣列的第一個元素為-1，最後一個元素為1000001。

接著從第二個元素開始，先找出陣列沒有被排序的位置r，如果陣列已經全部排序完成，直接輸出「yes」。

找到陣列沒有被排序的位置r之後，接著先嘗試使用交換元素的方式，看能不能找到一個位置l，與位置r的元素交換之後能將陣列全部排好。r和l的元素交換之後，他們相鄰的元素大小關係必須要正確，且換完之後，還需檢查其他元素是否也都排列完成。如果通過檢查，就輸出「swap l r」。

如果交換元素無法完成陣列排序的話，接下來要嘗試使用反轉子陣列的方式，看能不能在位置r之後找到一個位置l，將r到l的元素反轉後能將陣列全部排好。先找出r之後的反序陣列結束位置，接著判斷若將r和l交換之後(因為陣列要反轉)，l位置的元素是否大於l-1位置的元素，r位置的元素是否小於r+1位置的元素，如果皆是，表示反轉這個陣列是正確的。接著要判斷r+1位置之後是不是還有沒有被排序的位置，若有，則陣列無法只使用一次交換元素或是反轉子陣列的方式完成排序，輸出「no」；若沒有，則輸出「reverse l r」。

參考答案

import java.util.*;

class Solution {

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

        final int[] a = new int[n + 2];
        a[0] = -1;
        a[n + 1] = 1000001;
        for (int i = 1; i <= n; ++i) {
            a[i] = sc.nextInt();
        }
        int i = 1;
        int x = -1;
        while (i <= n) {
            if (a[i] > a[i + 1]) {
                x = i++;
                break;
            }
            ++i;
        }
        if (x >= 0) {
            // try swap
            boolean canSwap = false;
            int y = -1;
            while (i <= n) {
                int buffer = a[x];
                a[x] = a[i];
                a[i] = buffer;
                final int q = a[x - 1];
                final int p = a[x + 1];
                final int r = a[x];
                final int w = a[i];
                final int e = a[i - 1];
                final int t = a[i + 1];
                if ((q < r && r < p) && (e < w && w < t)) {
                    canSwap = true;
                    y = i++;
                    break;
                } else {
                    buffer = a[x];
                    a[x] = a[i];
                    a[i] = buffer;
                }
                ++i;
            }
            if (canSwap) {
                i = x + 1;
                while (i <= n) {
                    if (a[i] > a[i + 1]) {
                        canSwap = false;
                        final int buffer = a[x];
                        a[x] = a[y];
                        a[y] = buffer;
                        break;
                    }
                    ++i;
                }
            }
            if (canSwap) {
                System.out.println("yes\nswap " + x + " " + y);
                return;
            }

            // try reverse
            i = x + 1;
            while (i <= n) {
                if (!(a[i - 1] > a[i] && a[i] > a[i + 1])) {
                    y = i++;
                    break;
                }
                ++i;
            }
            boolean canReverse = a[x] < a[y + 1] && a[x - 1] < a[y];
            if (canReverse) {
                while (i <= n) {
                    if (a[i] > a[i + 1]) {
                        canReverse = false;
                        break;
                    }
                    ++i;
                }
            }
            if (canReverse) {
                System.out.println("yes\nreverse " + x + " " + y);
                return;
            }
            System.out.println("no");
        } else {
            System.out.println("yes");
        }
    }
}