Java程序占用太多内存

Question

这是我编写程序的问题

Ali baba did a trick on the forty thieves and was able to trap them inside a big cave which was the home of wild wolves. The thieves are without any weapons, only the chief of the thieves has knife. With no weapons they will not be able to fight with the wolves, so they decide to kill themselves rather than being eaten alive.

They all decide that they will stand in a circle and they every third person will kill himself but the chief of the thieves does not like this idea and has no intention of killing himself. He calculates where should he stand so that he is the last one left.

HackerMan wants to build a game based on this story, but instead of killing he decides that the participant will leave the game, and instead of every 3rd position it will be every 2nd position. Of course the number of participants will be much more than 40 in this game.

Input

The first line of input is an integer N (1 <= N <= 1000) that specifies the number of test cases. After that every line contains an integer X (5 <= X <= 100000000) which is the number of participants in the game.

Output

For each test case generate a line containing the position of the participant who survives. Assume that the participants have serial numbers from 1 to n and that the counting starts with person 1, i.e., the first person leaving is the one with number 2.

Sample Input

3 5 11 45

Sample Output

3 7 27

这是我的解决方案

class SurvivalStrategy {

    public int next;
    public int value;
    public boolean alive;

    SurvivalStrategy(int n, int v)
    {
        this.next = n;
        this.value = v;
        this.alive = true;
    }

    public int getNext(){
        return this.next;
    }
    public void kill(){
        this.alive = false;
    }

    public void changeNext(int n){
        this.next = n;
    }


    public static void main(String[] args) throws IOException {

        System.out.println("Enter the number of cases");
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        int N = Integer.parseInt(line);
        int[] array = new int[N];
        for(int a = 0; a < N; a++)
        {
            System.out.println("Enter No. of theives in case " + (a + 1));
            array[a] = Integer.parseInt(br.readLine());
        }
        for(int b = 0; b < N; b++)
        {
            try{

                int theives = 0;
                theives = array[b];
                SurvivalStrategy[] people = new SurvivalStrategy[theives];
                int i = 0;
                int nextctr = 2;
                for(i = 0; i < people.length; i++)
                {
                    people[i] = new SurvivalStrategy(nextctr, i + 1);

                    if(nextctr > people.length)
                    {
                        people[i] = new SurvivalStrategy(1, i + 1);
                    }
                    nextctr++;
                }

                int k = 0;
                int nextguy = 0;
                int survivers = people.length;
                boolean CarryOnJatta = true;
                int lastSurviver = 0;
                while(CarryOnJatta)
                {
                    if(k >= people.length)
                    {
                        k = 0;
                        k = k + 2;
                    }
                    if(people[k].alive)
                    {
                        //System.out.println(people[k].value + " is Alive");
                        nextguy = people[k].getNext();
                        if(people[nextguy - 1].alive)
                        {
                            people[nextguy - 1].kill();

                            people[k].changeNext(people[nextguy - 1].next);
                            lastSurviver = people[k].value;
                            survivers--;
                        }else{
                            k = k + 2;
                        }
                        k = k + 2;
                    }else{
                        k = k + 2;
                    }

                    if (survivers == 1)
                    {
                        CarryOnJatta = false;
                        System.out.println("" + lastSurviver);

                    }
                }




            } catch(Exception e)
            {
                e.printStackTrace();
            }
        }
    }
}

我的程序为小值提供输出，但不为大值提供输出。如果我用输入 (23987443) 尝试它，我会得到 java heap size exceeded 错误。有什么办法可以改善这个程序的空间和时间复杂度。如果其他算法生成所需的输出，我也对它们持开放态度。

Answer 1

您在堆上至少分配了 23987443 * sizeof(SurvivalStrategy) 内存 - 每个案例大约需要 300MB，并且仅在这行代码之前:

SurvivalStrategy[] people = new SurvivalStrategy[theives];

我想这个挑战旨在教你高效内存处理的优点 - 所以你不需要一次分配整个内存，你需要一个接一个地处理你的项目，这样你一次只分配几个项目, 让 GC 收集不再需要的。