は、私がhackerrank問題で「ほぼソート」の挑戦を解決しようとしているhackerrankチャレンジ

Question

を解決するのに役立つが必要です：要素を持つ配列を指定して

、あなたはの一つだけを使用して昇順で、この配列をソートすることができます次の操作は？

2つの要素を入れ替えます。 1つのサブセグメントを反転させます。

入力形式 最初の行には、配列のサイズを示す1つの整数が含まれています。

次の行には、スペースで区切られた整数が含まれます。

サンプル入力＃1

サンプル出力＃1

はい
スワップ1 2

サンプル入力＃2

サンプル出力＃2

ない

サンプル入力＃3

サンプル出力＃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

、ソートされたアレイとして元の配列とBとしてA渡します。

---

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：

あなたはあまりにも多く、ここでWAYをやっています！あなたは、（一見して）すべての可能なケースを強制的に強制するようです。

代わりに、地域のすべての番号が異なる場合があります。 より2つ以上の場合は、またはより多くの要素が1つ以上の要素で区切られている場合は、すぐにfalseを返します。

上記の「複数」の理由は、奇数長領域のためです - 中要素は同じです。このような2つの領域を見つけたら、それらを1つとして扱います。次に、地域が逆転しているかどうかを調べることができます。

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; 
} 

---

ただ、あなたのパフォーマンスの向上のアイデアを与えるために、新しいものがちょうど0.1秒かかったのに対し、ideone.comに、150の配列の長さで、CheckSingleReverseの最初の実装は、1.83秒を要しました。 250の長さでは、実際にはがを超過しましたが、計算時間（5秒）は新しいものがわずか0.12秒でした。

これは、実装が指数関数的な時間を要するのに対して、私の場合は線形時間（並べ替えを無視する）であるようです。

Funnily十分、3 の配列サイズで私はまだ周りに0.26秒を取得しています（ideoneの実行時間は、同様に需要によるちゃったごめんなさいを少し変動）