java - min nm 以便对整个数组进行排序

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 坐标 -> 数组的值），那么图表将如下所示：

现在，如果我们看到图表，有两个地方发生下降，一个在 10 之后，另一个在 16 之后。现在在之字形部分，如果我们看到最小值为 6，最大值为 16。所以我们应该排序的部分使整个数组排序在 (6,16) 之间。请参考下图：

现在我们可以轻松地将数组分成三部分。中间部分是我们要排序的部分，以便对整个数组进行排序。请提供您宝贵的意见。我试图最好地向我的标签解释，如果我想解释更多，请告诉我。等待有价值的输入。

下面的代码实现了上面的逻辑：

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

}

但是，我看到结果与您的解决方案@Trying 不一样，我误解了这个问题吗？顺便说一句，在您的代码中，它会打印

4 : 9
6 : 16

这些是什么？哪些是指数？

谢谢。

编辑：通过添加标记为 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

实际上，您可以有两个指针，最后一个指针向后移动以检查最短未排序序列的起始索引。这是一种 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};
    }