分のn-mの私はインタビューの中で、以下の質問をした

Question

、アレイ全体がソートされるように：

Given an array of integers, write a method to find indices m and n such that 
if you sorted elements m through n, the entire array would be sorted. Minimize 
n-m. i.e. find smallest sequence. 

下記の私の答えを見つけ、解決にコメントをしてください。ありがとう!!!

Answer 1

最後に私は問題の解決策を得ました。お気軽にコメントしてください。

例をみましょう：私は、グラフの中でこれを置く場合

int a[] = {1,3,4,6,10,6,16,12,13,15,16,19,20,22,25} 

は今（X座標 - >配列のインデックスとY座標 - >配列の値）、グラフは、などのようになります。以下：我々はグラフを見れば

は今、ディップは、我々は最小値が6で最大valが16で見れば1がジグザグ部分に今16の後に10と別の後で起こる2つの場所があります。したがって、配列全体をソートするためにソートする必要がある部分は（6,16）の間です。下の画像を参照してください：

今、私たちは簡単に3部までの配列を分割することができます。そして、配列全体がソートされるようにソートしたい部分の中間部分。貴重な情報を提供してください。私は自分のレーベルに最高のことを説明しようとしたが、もっと説明したいのなら教えてください。貴重な入力を待っています。

以下のコードは、上記のロジックを実装します。

public void getMN(int[] a) 
{ 
    int min = Integer.MAX_VALUE; int max = Integer.MIN_VALUE; 
    for(int i=1; i<a.length; i++) 
    { 
     if(a[i]<a[i-1]) 
     { 
      if(a[i-1] > max) 
      { 
       max = a[i-1]; 
      } 
      if(a[i] < min) 
      { 
       min = a[i]; 
      } 
     } 
    } 
    if(max == Integer.MIN_VALUE){System.out.println("Array already sorted!!!");} 
    int m =-1, n =-1; 
    for(int i=0; i<a.length; i++) 
    { 
     if(a[i]<=min) 
     { 
      m++; 
     } 
     else 
     { 
      m++; 
      break; 
     } 
    } 
    for(int i=a.length-1; i>=0; i--) 
    { 
     if(a[i]>=max) 
     { 
      n++; 
     } 
     else 
     { 
      n++; 
      break; 
     } 
    } 
    System.out.println(m +" : "+(a.length-1-n)); 
    System.out.println(min +" : "+max); 
} 

Answer 2

は実は、私はそのような何かを思い付いた：

public static void sortMthroughN(int[] a) 
{ 
    int m = -1; 
    int n = -1; 
    int k = -1; 
    int l = -1; 
    int biggest; 
    int smallest; 
    // Loop through to find the start of the unsorted array. 
    for(int i = 0; i < a.length-1; i++) 
     if(a[i] > a[i+1]) { 
      m = i; 
      break; 
     } 
    // Loop back through to find the end of the unsorted array. 
    for(int i = a.length-2; i > 0; i--) 
     if(a[i] > a[i+1]) { 
      n = i; 
      break; 
     } 
    biggest = smallest = a[m]; 
    // Find the biggest and the smallest integers in the unsorted array. 
    for(int i = m+1; i < n+1; i++) { 
     if(a[i] < smallest) 
      smallest = a[i]; 
     if(a[i] > biggest) 
      biggest = a[i]; 
    } 

    // Now, let's find the right places of the biggest and smallest integers. 
    for(int i = n; i < a.length-1; i++) 
     if(a[i+1] >= biggest) { 
      k = i+1;  //1 
      break; 
     } 

    for(int i = m; i > 0; i--) 
     if(a[i-1] <= smallest) {        
      l = i-1; //2 
      break; 
     } 
      // After finding the right places of the biggest and the smallest integers 
      // in the unsorted array, these indices is going to be the m and n. 
    System.out.println("Start indice: " + l); 
    System.out.println("End indice: " + k); 

} 

しかし、私は結果があなたの解決策と同じではないことがわかり@試してみましたが、私はその質問を誤解しましたか？ところで、あなたのコードでは、それは印刷されます

4 : 9 
6 : 16 

これは何ですか？どちらが指標ですか？

ありがとうございました。

EDIT：1本としてマークされた場所を追加することにより：

  if(a[i+1] == biggest) { 
       k = i; 
       break; 
      } 

と2：

 if(a[i+1] == smallest) { 
      l = i; 
      break; 
     } 

それが良いです。

Answer 3

それは、配列の終わりから始まる最大値を見つけるために簡単です：

public void FindMinSequenceToSort(int[] arr) 
{ 
    if(arr == null || arr.length == 0) return; 

    int m = 0, min = findMinVal(arr); 
    int n = arr.length - 1, max = findMaxVal(arr); 

    while(arr[m] < min) 
    { 
     m ++; 
    } 

    while(arr[n] > max) 
    { 
     n --; 
    } 

    System.out.println(m); 
    System.out.println(n); 
} 

private int findMinVal(int[] arr) 
{ 
    int min = Integer.MAX_VALUE; 
    for(int i = 1; i < arr.length; i++) 
    { 
     if(arr[i] < arr[i-1] && arr[i] < min) 
     { 
      min = arr[i]; 
     } 
    } 

    return min; 
} 

private int findMaxVal(int[] arr) 
{ 
    int max = Integer.MIN_VALUE; 
    for(int i = arr.length - 2; i >= 0; i--) 
    { 
     if(arr[i] >= arr[i+1] && arr[i] > max) 
     { 
      max = arr[i]; 
     } 
    } 

    return max; 
} 

Answer 4

実際には、次の2つのポインタを持つことができますし、最後のポインタが最短ソートされていないシーケンスのインデックスを開始チェックするために後退。それはO（N2）のようなものですが、よりクリーンです。

public static int[] findMinUnsortedSequence(int[] array) { 
     int firstStartIndex = 0; 
     int startIndex = 0; 
     int endIndex = 0; 
     for (int i = 0; i < array.length; i++) { 
      for (int j = 0; j < i; j++) { 
       if (array[j] <= array[i]) { 
        startIndex = j + 1; 
       } else { 
        endIndex = i; 
        if (firstStartIndex == 0) { 
         firstStartIndex = startIndex; 
        } 
       } 
      } 
     } 
     return new int[]{firstStartIndex, endIndex}; 
    }