0

问题是删除每个第二个元素，直到最后一个元素保留。（假设元素被放置在圆圈中）

我的程序适用于较小的 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);

您也可以使用 aList<Integer>代替，因为这是列表实际包含的内容。

但是一个巨大的字符串列表需要大量的内存。扩大堆大小

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 的最大幂，使得 2^m <= n

那么获胜者是 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]

老实说，我自己并没有想出解决方案，但记得在“具体数学”一书中读过约瑟夫斯问题（谷歌会找到 PDF，查看第 1.3 节）

于 2013-03-09T23:54:58.010 回答