4

送信された配列の最大の整数値である int を返すメソッドを作成しようとしています。このメソッドを機能させる方法は、配列の最初と最後の要素を for ループでチェックし、途中まで処理することです。したがって、i = 最初の整数、k = 最後の整数です。いつi = 0, k = n-1（インデックス）、いつi = 1, k = n-2私のドリフトをキャッチするか。すべてのループで、チェックする必要がありますif a[i]>a[k]。それから彼らは場所を変えます。次に、最大数が配列の先頭半分にあることがわかっているので、その半分をチェックしたいので、最終的に最大の int はインデックス 0 にあります。

私はこのように試しました：

public static int maxOfArray(int[] a)
{
    int length = a.length;

    if(length<1)
        throw new NoSuchElementException("Not at least one integer in array");

    while (length > 1)
    {
        int k = length;

        for(int i = 0; i < length/2; i++)
        {
            k--;

            if(a[i]<a[k])
            {
                int j = a[i];
                a[i] = a[k];
                a[k] = j;
            }
        }
        length /=2;
    }
    return a[0];
}

..しかし、よくわかりません..ここで何が起こっているのかを「想像する」のに苦労しています..しかし、常に機能しているわけではありません..（時々ですが）.

EDIT も：配列{6,15,2,5,8,14,10,16,11,17,13,7,1,18,3,4,9,12}; 最大数として 17 を吐き出します。奇数長のバグを修正する必要があることはわかっていますが、最初にこの偶数長の配列を解決したいと思います..

4

9 に答える 9

7

バグとは出会いlengthが変な時です。

このような場合、中間要素を「見逃し」ます。

例: 入力int[] arr = { 8, 1, 5, 4, 9, 4, 3, 7, 2 };の場合 - 要素9はそれ自体と比較およびチェックされますが、次に のサイズを縮小すると、次に反復する配列からlength除外されます。9

ceil(length/2)問題をの代わりにlength/2(および の特殊なケースを処理するlength==1)に減らすことで解決できると思います

コメントで言及されたもう 1 つの問題は、 までではなくまで繰り返すlength/2length必要があることです。

最後に -符号が間違っています。

if(a[i]>a[k])

する必要があります

if(a[i]<a[k])

覚えておいてください-最初の要素が2番目の要素よりも小さい場合、要素を交換して、より大きな要素を配列の先頭にプッシュしようとしています。

于 2012-09-11T11:20:20.507 に答える
3

しかし、私は本当にそれを理解していません..私はここで何が起こっているのかを「想像する」のに苦労しています..

その場合、デバッガーを使用してコードをステップ実行し、コードの各行の動作を把握する必要があります。

私がすることは次のとおりです。

public static int maxOfArray(int[] a) {
    int max = a[0];
    for (int i : a)
        if (max < i)
            max = i;
    return max;
}

public static int findMaxTheHardWay(int[] array) {
    for (int length = array.length; length > 1; length = (length + 1) / 2) {
        for (int i = 0; i < length / 2; i++) {
            if (array[i] < array[length - i - 1])
                array[i] = array[length - i - 1]; // don't need to swap.
        }
    }
    return array[0];
}

public static void main(String... args) {
    Random rand = new Random(1);
    for (int i = 1; i <= 1000; i++) {
        int[] a = new int[i];
        for (int j = 0; j < i; j++) a[j] = rand.nextInt();
        int max = maxOfArray(a);
        int max2 = findMaxTheHardWay(a);
        if (max != max2)
            throw new AssertionError(i + ": " + max + " != " + max2);
    }
}
于 2012-09-11T11:08:21.747 に答える
3

これは問題を解決するためのかなりクレイジーな方法ですが、私は一緒に遊んでいきます.

問題は内側のループにあります。

  • i = 0 および k = 長さ - 1 から始めます。
  • a[i] > a[k] の場合、それらを交換します。
  • ...
  • k = 0 と i = 長さ - 1 になります。
  • a[i] > a[k] の場合、それらを交換します。

これを注意深く見ると、最初のスワップで要素をスワップした場合、最後のスワップでもそれらをスワップすることに気付くでしょう。つまり、最初のスワップの効果を元に戻します。そして、同じことが配列スライス全体を通してペアワイズに適用されます。

見る？

あなたがする必要があるのは、内側のループを途中で止めることです...そしてlengthが奇数の場合を考慮に入れます。

ちなみに、私がこれを「ややクレイジー」と呼んだ理由は、明白で単純な方法の方がはるかに高速だからですO(N)。O(NlogN)

于 2012-09-11T11:29:33.057 に答える
1 
int a[] = {1,7,3};   
List<Integer> list = Arrays.asList(a);  
Integer largest = Collections.max(list);

これにより、配列内の最大数が得られます。

于 2012-09-11T11:23:32.173 に答える
1

これは、あなたが望む仕様に適合するソリューションです（ここにある他の多くのものとは異なり、うーん、うーん）：

    final Integer[] input = {1, 2, 6, 32, 4, 44 ,12, 42, 3, 7, 17, 22, 57, 23, 102, 103 };

    int half = (input.length / 2);
    int mod = input.length % 2;
    while (half >= 0) {
        for (int i = 0, j = (half * 2) + mod - 1; i <= half && j >= half; i++, j--) {
            if (input[i] < input[j]) {
                final int tmp = input[i];
                input[i] = input[j];
                input[j] = tmp;
            }
        }
        if (half == 0) break;
        half = half / 2;
        mod = half % 2;
    }
    //Here, input[0] = the biggest number in the original input.

編集：modを追加したので、最後の要素が最大の場合に機能します..

于 2012-09-11T11:25:46.123 に答える
1

あなたのコードは機能していると思います.奇数配列の場合は長さ/ 2を天井にする必要がありますが、私のテストは適切な結果を返します:

package org.devince.largestinteger;

import java.util.NoSuchElementException;

public class LargestInteger {
    final static int[] input = {1, 2, 6, 32, 4, 44 ,12, 42, 3, 7, 17, 22, 57, 23, 102, 103 };
//  final static int[] input = { 8, 1, 5, 4, 9, 4, 3, 7, 2 };
//  final static int[] input = {1,3,7};

    /**
     * @param args
     */
    public static void main(String[] args) {
        System.out.println(String.valueOf(maxOfArray(input)));
    }

    public static int maxOfArray(int[] a)
    {
        int length = a.length;

        if(length<1)
            throw new NoSuchElementException("Not at least one integer in array");

        while (length > 1)
        {
            int k = length;

            for(int i = 0; i < length; i++)
            {
                k--;

                if(a[i]>a[k])
                {
                    int j = a[i];
                    a[i] = a[k];
                    a[k] = j;
                }
            }
            length = (int) Math.ceil(length / 2f);
        }
        return a[0];
    }

}
于 2012-09-11T11:57:02.860 に答える
0

配列の最初の値を variable に格納するだけではどうですかmax。

その後、2 番目の位置から最後の まで配列をループし、ループで現在の値がより大きいかどうかを確認します。大きい場合は、その値maxを割り当てるだけmaxです。

戻るmaxと、最大数になります。 

public int FindLargest()
{
    int[] num = { 1, 2, 5, 12, 13, 56, 16, 4 };
    int max = num[0];

    for (int i = 1; i <num.length; i++)
    {
        if (num[i] > max)
        {
            max = num[i];
        }
    }

    return max;
}
于 2012-09-11T11:12:41.493 に答える
0

同じようにアプローチすることもできます。

int length = a.length;
   while (length > 1)
    {
        int k = length;
        for(int i = 0; i < length; i++)
        { 
            for(int y = k-1; y >= i; y--) 
            {         
                if(a[i]<a[y])
                {
                    int j = a[i];
                    a[i] = a[y];
                    a[y] = j;               
                }
            }       
        }
        length /=2;
    }
于 2012-09-11T12:08:43.717 に答える