[HackerRank]拉里的陣列(Larry's Array)

題目描述

拉里有一串N個數字的陣列A，A={a₁,a₂,…,a_N-1,a_N}，每個數字a_i都是獨特不重複的。拉里想要用他的機器人來排序這個陣列A，他的機器人可以不限次數地任意旋轉某3個連續相同的元素，舉例來說：ABC旋轉一次之後會變成BCA，再旋轉一次會變成CAB，再旋轉一次又會回到ABC。

如果A={1,6,5,2,4,3}，然後機器人旋轉了(6,5,2)，A的內容就會變成{1,5,2,6,4,3}。

計算每組測試資料，並在新的一行輸出拉里的機器人是否可以成功排序陣列A。如果可以，輸出「YES」；如果不行，輸出「NO」。

原題網址

https://www.hackerrank.com/challenges/larrys-array

輸入格式

輸入第一行包含一個整數T，為測試資料的數量，範圍在1到10之間(包含1和10)。
接下來的的2T行，每兩行表示一組測試資料。一組測試資料的第一行是一個整數N，為A陣列的大小，範圍在3到1000之間(包含3和1000)。第二行輸入N個整數表示A陣列的內容，可以用a_i來表示輸入的元素數值，數值範圍在1到N之間(包含1和N)，每個元素的數值都不相同。

輸出格式

計算每組測試資料，並在新的一行輸出拉里的機器人是否可以成功排序陣列A。如果可以，輸出「YES」，否則輸出「NO」。

範例輸入

3
3
3 1 2
4
1 3 4 2
5
1 2 3 5 4

範例輸出

YES
YES
NO

額外解釋

用A_j表示每次旋轉後A陣列的內容。

測試資料1：

A₀={3,1,2}→rotate(3,1,2)→A₁={1,2,3}

A陣列已經排序好了，因此輸出「YES」。

測試資料2：
A₀={1,3,4,2}→rotate(3,4,2)→A₁={1,4,2,3}
A₁={1,4,2,3}→rotate(4,2,3)→A₂={1,2,3,4}
A陣列已經排序好了，因此輸出「YES」。

測試資料3：
沒有辦法將A陣列排序好，輸出「NO」。

解題概念

可以把這題所用到的演算法，當作是氣泡排序法(Bubble Sort)的改版。原始的氣泡排序法一次旋轉兩個元素，而這裡用到的演算法一次需旋轉三個元素。我們可以從第一個元素(陣列索引0)開始，由陣列的最尾端開始往前旋轉，把最小的數值旋轉至第一個元素的位置。接著再從第二個元素(陣列索引1)開始，由陣列的最尾端開始往前旋轉，把最小的數值旋轉至第二個元素的位置，如此一來就可以完成這三旋轉的氣泡排序法。

至於該如何判斷這三旋轉的氣泡排序法是否排序成功，只需要在排到最後時，判斷最後兩個元素的順序是否正確即可，因為在這最後兩個元素之前的元素都已經確定排序好了。

參考答案

import java.util.Scanner;

public class Solution {

    public static void main(String[] args) {
        final Scanner sc = new Scanner(System.in);
        int testCase = sc.nextInt();
        TestCase:
        while (testCase-- > 0) {
            final int n = sc.nextInt();
            final int[] a = new int[n];
            for (int i = 0; i < n; ++i) {
                a[i] = sc.nextInt();
            }
            final int n_dec3 = n - 3;
            for (int i = 0; i <= n_dec3; ++i) {
                for (int j = n_dec3; j >= i; --j) {
                    final int x = a[j];
                    final int y = a[j + 1];
                    final int z = a[j + 2];
                    if (z <= y && z <= x) {
                        a[j] = z;
                        a[j + 1] = x;
                        a[j + 2] = y;
                    } else if (y <= x && y <= z) {
                        a[j] = y;
                        a[j + 1] = z;
                        a[j + 2] = x;
                    } else{
                        // don't need to rotate
                    }
                }
            }
            System.out.println(a[n - 2] <= a[n - 1] ? "YES" : "NO");
        }
    }
}

import java.util.Scanner;

public class Solution {

public static void main(String[] args) {

final Scanner sc = new Scanner(System.in);

int testCase = sc.nextInt();

TestCase:

while (testCase-- > 0) {

final int n = sc.nextInt();

final int[] a = new int[n];

for (int i = 0; i < n; ++i) {

a[i] = sc.nextInt();

}

final int n_dec3 = n - 3;

for (int i = 0; i <= n_dec3; ++i) {

for (int j = n_dec3; j >= i; --j) {

final int x = a[j];

final int y = a[j + 1];

final int z = a[j + 2];

if (z <= y && z <= x) {

a[j] = z;

a[j + 1] = x;

a[j + 2] = y;

} else if (y <= x && y <= z) {

a[j] = y;

a[j + 1] = z;

a[j + 2] = x;

} else{

// don't need to rotate

}

System.out.println(a[n - 2] <= a[n - 1] ? "YES" : "NO");

}

MagicLen