0

問題は、最後の要素が残るまで、2 つおきの要素を削除することです。(要素が円形に配置されていると仮定)

私のプログラムは n の値が小さい場合は正常に動作しますが、大きな値を使用するとjava.lang.OutOfMemoryError: Java heap spaceメッセージが表示されます。

コードをより効率的にしてこのエラーを解決するために何をする必要があるかについて、私を助けてくれる人がいます。

ありがとう！

import java.util.*;

public class ArrayLists {
    public static void main(String[] args) {
        ArrayList myList = new ArrayList();
        int n = 23987443;
        for (int i = 1; i <= n; i = i + 2) {
            myList.add("" + i);
        }

        Object x = myList.get(myList.size() - 1);
        Object y = myList.get(myList.size() - 1);
        while (myList.size() != 1) {
            if (x == y) {
                for (int i = 0; i <= myList.size() - 1; i++) {
                    myList.remove(i);
                }
            } 
            else {
                x = y;
                for (int i = 1; i <= myList.size() - 1; i++) {
                    myList.remove(i);
                }
            }
            y = myList.get(myList.size() - 1);
        }
        System.out.println("Winner:" + myList);
    }
}
4

3 に答える 3

2

文字列の膨大なリストを作成しています。したがって、すべてのリストを保持するのに十分なメモリが必要になります。リストを適切なサイズで初期化し、リストを拡大するための一時的なコピーを回避することで、消費を抑えることができます。

int n = 23987443;
List<String> myList = new ArrayList<String>(23987443);

List<Integer>リストには実際に a が含まれているため、代わりにa を使用することもできます。

しかし、文字列の膨大なリストには大量のメモリが必要です。でヒープサイズを拡大

java -Xmx1024m ...

例 (1024 MB のヒープ)

于 2013-03-09T22:40:06.800 に答える
1

O(N * log N)これはより少ないメモリを使用しますが、代わりに引用が少し速くなりますO(N^2 * log N)

public static void main(String[] args) {
    // for (int n = 1; n < 400; n++) {
    int n = 23987443;
    System.out.print(n + ": ");
    result(n);
    // }
}

private static void result(int n) {
    List<Integer> myList = new ArrayList<>(), myList2 = new ArrayList<>();
    for (int i = 1; i <= n; i = i + 2) {
        myList.add(i);
    }

    Integer x = myList.get(myList.size() - 1);
    Integer y = myList.get(myList.size() - 1);
    while (myList.size() != 1) {
        if (x == y) {
            for (int i = 1; i < myList.size(); i += 2) {
                myList2.add(myList.get(i));
            }
        } else {
            x = y;
            for (int i = 0; i <= myList.size() - 1; i += 2) {
                myList2.add(myList.get(i));
            }
        }
        List<Integer> tmp = myList2;
        myList2 = myList;
        myList = tmp;
        myList2.clear();

        y = myList.get(myList.size() - 1);
       // System.out.println("\t" + myList);
    }
    System.out.println("Winner:" + myList.get(0));
}

注：代わりにTIntArrayListを使用するArrayList<Integer>と、メモリの約1/5が使用されます。

于 2013-03-09T23:12:13.707 に答える
0

リストの要素数を次のように記述した場合、問題の答えは閉じた形式で計算できます。

n = 2^m + l

ここで、m は 2^m <= n となる 2 の最大累乗です。

勝者は w = 2*l + 1 です。

そこで、より効率的なプログラムを次に示します。

public class ArrayLists {
  public static void main(String[] args) {
    int n = 23987443;
    int pow = Integer.highestOneBit(n);
    int l = n - pow;
    System.out.println("Winner:[" +((2*l)+1)+"]" );
  }
}

その n の値に対する答え:

Winner:[14420455]

正直なところ、私は自分で解決策を思いつきませんでしたが、「具体的な数学」という本でヨセフスの問題について読んだことを思い出しました (Google は PDF を見つけます。セクション 1.3 をチェックしてください)。

于 2013-03-09T23:54:58.010 に答える