31 Almost Sorted Array

kamia

很坑的一题，主要注意元素相等时的判断。
思路是，分别从左边和右边扫描数组，找到第一个违反sort规则的元素。如果这个元素有重复，则要找最左和最右的那个元素。
另外，reverse可以归结到swap。所以找到最左和最右的那个元素，就swap中间的元素。最后再检查一遍看看swap后的是不是有序即可。

提供几个test case：
//        int[] a = {2,2,10,2};
//        int[] a = {2,2,10,2,2};
//        int[] a = {1,2,1,2,2};
//        int[] a = {1,1,3,3,3};
//        int[] a = {3,3,2,2};
//        int[] a = {3,2,2};
//        int[] a = {};
都应该返回true


时间复杂度O（n）

1.     // https://www.hackerrank.com/challenges/almost-sorted
   
2.     public static boolean isAlmostSorted(int [] a) {
   
3.         if(a.length == 0)   return true;
   
4.         int left = 0, right = a.length - 1;
   
5.         // try to store swap region as far as possible
   
6.         for(int i=1; i<a.length; i++) {
   
7.             if(a[i-1] == a【i】)  left = i-1; // store leftmost
   
8.             else if(a[i-1] > a【i】) {
   
9.                 if((a[i-1] != a[left]))
   
10.                     left = i - 1;
    
11.                 break;
    
12.             }
    
13.         }
    
14.         for(int j=a.length-2; j>=0; j--) {
    
15.             if(a[j] == a[j+1])  right = j+1;    // store rightmost
    
16.             else if(a[j] > a[j+1]) {
    
17.                 if(a[right] != a[j+1])
    
18.                     right = j + 1;
    
19.                 break;
    
20.             }
    
21.         }
    
22. 
    
23.         while(left <= right) {
    
24.             if(a[left] > a[right])
    
25.                 swap(a, left, right);
    
26.             left++;
    
27.             right--;
    
28.         }
    
29. 
    
30.         // check if sorted
    
31.         for(int i=1; i<a.length; i++) {
    
32.             if(a[i-1] > a【i】) {
    
33.                 return false;
    
34.             }
    
35.         }
    
36. 
    
37.         return true;
    
38.     }
    
39. 
    
40.     private static void swap(int[] a, int left, int right) {
    
41.         int tmp = a[left];
    
42.         a[left] = a[right];
    
43.         a[right] = tmp;
    
44.     }

复制代码

lubor

感觉这个题目描述有点confusing啊，我最开始理解成可以使用两次operation呢（两种operation每个各一次）。后来看了答案才知道是只能使用either in the following operations.