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.

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

4

4 に答える 4

9

最後に、問題の解決策を見つけました。お気軽にコメントしてください。

例を見てみましょう:

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

これをグラフに入れると (X 座標 -> 配列インデックスおよび Y 座標 -> 配列の値)、グラフは次のようになります。 ここに画像の説明を入力

グラフを見ると、ディップが発生する場所が 2 つあります。1 つは 10 の後、もう 1 つは 16 の後です。ジグザグ部分では、最小値が 6 で最大値が 16 であることがわかります。配列全体をソートするのは (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);
}
于 2013-04-06T20:28:31.777 に答える
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;
         }

それはさらにいいです。

于 2013-04-06T21:44:24.767 に答える
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;
}
于 2015-02-15T18:39:16.943 に答える
0

実際には、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};
    }
于 2015-08-17T20:27:04.427 に答える