題目描述

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



交換兩個元素
反轉子陣列

原題網址

https://www.hackerrank.com/challenges/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

2
4 2

範例輸出1

yes
swap 1 2

範例輸入2

3
3 1 2

範例輸出2

no

範例輸入3

6
1 5 4 3 2 6

範例輸出3

yes
reverse 2 5

額外解釋

第一個範例中,您可以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");
        }
    }
}