phút n-m sao cho toàn bộ mảng sẽ được sắp xếp

Question

Tôi đã hỏi những câu dưới đây trong một cuộc phỏng vấn:

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. 

tìm câu trả lời của tôi dưới đây và hãy làm bình luận về các giải pháp. Cảm ơn!!!

Answer 1

Cuối cùng tôi đã có giải pháp cho vấn đề, vui lòng bình luận.

Hãy lấy một ví dụ:

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

Bây giờ nếu tôi sẽ đặt này vào đồ thị (X-phối hợp -> chỉ số mảng và Tọa độ Y -> giá trị của mảng) thì biểu đồ sẽ trông giống như như bên dưới:

Bây giờ, nếu chúng ta thấy biểu đồ có hai vị trí xảy ra sau 10 và khác sau 16. Bây giờ trong phần zag zag nếu chúng ta thấy giá trị nhỏ nhất là 6 và giá trị tối đa là 16. Vì vậy, phần mà chúng ta nên sắp xếp để làm cho toàn bộ mảng được sắp xếp là giữa (6,16). Vui lòng tham khảo hình dưới đây:

Bây giờ chúng ta có thể dễ dàng chia mảng trong ba phần. Và phần giữa chúng ta muốn sắp xếp sao cho toàn bộ mảng sẽ được sắp xếp. Vui lòng cung cấp đầu vào có giá trị của bạn. Tôi đã cố giải thích cho nhãn hiệu của mình tốt nhất, vui lòng cho tôi biết nếu tôi muốn giải thích thêm. Đang đợi đầu vào có giá trị.

Mã dưới đây thực hiện logic trên:

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

Thực ra, tôi đã đưa ra một cái gì đó như thế:

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

} 

Nhưng, tôi thấy rằng kết quả này là không giống với giải pháp của bạn @ Đang cố gắng, tôi đã hiểu sai câu hỏi chưa? Nhân tiện, tại và mã của bạn, nó in

4 : 9 
6 : 16 

Đây là những gì? Cái nào là chỉ số?

Cảm ơn.

EDIT: bằng cách thêm vị trí đánh dấu là 1 này:

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

và 2:

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

nó là tốt hơn.

Answer 3

Nó dễ dàng hơn để tìm giá trị tối đa bắt đầu từ cuối của mảng:

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

Trên thực tế, bạn có thể có hai con trỏ và con trỏ cuối cùng di chuyển lạc hậu để kiểm tra bắt đầu chỉ số của chuỗi được phân loại ngắn nhất. Đó là loại O (N2) nhưng nó sạch hơn.

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