需要幫助解決

Question

我想在hackerrank要解決的問題是「幾乎排序」的挑戰是hackerrank挑戰：

考慮到與元素的數組，你可以使用排序中只有一個數組升序以下操作？

交換兩個元素。 反轉一個子段。輸入格式 第一行包含一個整數，它表示數組的大小。

下一行包含用空格分隔的整數。

樣品輸入＃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

對於下面的代碼，在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：

你正在做WAY太多了！你似乎是蠻橫逼迫每一個可能的情況（乍一看）。

你可以做的是找到區域其中所有數字都不相同。如果有多於這兩個這兩個或者兩個相隔多於一個元素，則立即返回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的執行時間波動了一下爲好，由於probs需求）