需要帮助解决

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需求）