logo标签列表

使整个数组排序所需的最小 n-m 值

javaalgorithm
5

我在一次面试中被问到以下问题：

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.

请在下面找到我的答案，并对解决方案进行评论。谢谢!!!
1
请随意回答您自己的问题！但请确保将它们分开。我建议您在此问题下添加一个答案，然后编辑问题，只留下您的问题。 - user1131435
我无法理解你的观点。抱歉。 - Trying
一个问题应该只是一个问题。请编辑您的问题，使其仅包含您的问题。然后，您可以使用“您的答案”框正常回答自己的问题。 - user1131435
@Telthien 我完成了!!! - Trying
不错！顺便说一下，这是个有趣的解决方案！ - user1131435
4个回答
9
最后我找到了解决该问题的方法，请随意评论。
让我们举个例子：
int a[] = {1,3,4,6,10,6,16,12,13,15,16,19,20,22,25}

现在，如果我将此内容放入图形中（X坐标-〉数组索引和Y坐标-〉数组的值），则图形将如下所示： enter image description here 现在，如果我们看一下这个图形，就会发现有两个位置出现了下降，一个是10之后，另一个是16之后。现在，在锯齿状部分中，如果我们看一下最小值为6，最大值为16。因此，我们应该对（6,16）之间的部分进行排序，以使整个数组排序。请参考以下图片:

enter image description here

现在，我们可以轻松地将数组分为三个部分。中间部分是我们想要排序的部分，以便整个数组都被排序。请提供有价值的意见。我尽力向我的标签解释清楚，请让我知道是否需要更多的解释。等待有价值的意见。
以下代码实现上述逻辑：
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);
}
添加注释，让新手也能轻松理解代码 - roottraveller
1
从数组末尾开始查找最大值更容易：
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;
}
1
实际上，我想到了这样的东西：
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;
         }

它更好。

4 是排序将开始的起始索引，即 10 的位置，最后一个索引是 9，即当前位置为 15。未排序数组的最小值为 6，最大值为 16。希望这可以澄清事情！ - Trying
好的，没问题。:) 3 是起始索引，10 是结束索引。我想，我在等式方面有问题。顺便说一句，解决方案很不错。;) - sha1
1
我从0开始设置数组索引。根据我的算法，最小值为6，最大值为16，由于我需要将n-m最小化，因此我忽略了分别位于第10和第3个位置的6和16。因此，排序子部分从4到9（包括4和9）开始。清楚吗？还是我漏掉了什么？ - Trying
1
你是否与我的解决方案保持同步，还是不同意它？因为我们都在同时学习。 - Trying
你的答案是正确的。在编辑我的代码之前，我发现答案是3、10；因为我没有注意到等号部分。如果相等（或减少）则增加索引是正确的方法。我通过添加这两部分代码来解决问题。 - sha1
我认为你应该添加这行代码 l = m, k = n; - roottraveller
0
其实，你可以有两个指针，最后一个指针向后移动以检查最短未排序序列的起始索引。这有点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};
    }
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接