java - 打乱 LinkedList 时出现 ArrayIndexOutOfBoundsException

Question

好的，我有一个作业，它是这样的:

Assume you have as input a singly-linked list containing N items (an instance of a LinkedList class in Java). You should rearrange the items in the LinkedList uniformly at random. Your algorithm should consume a logarithmic (or constant) amount of extra memory and run in time proportional to NlogN in the worst case.

对于算法，我要进行合并排序，当它合并时以随机方式进行。 但我的程序陷入了困境，因为它抛出了 ArrayIndexOutOfBoundsException ，但它不在我的代码中，而是在 LinkedList.java 中

我对 LinkedList 不太熟悉，所以我不知道该怎么做，我什至不确定我是否以正确的方式这样做。

代码:

import java.util.LinkedList;

public class Q02 {

public static void main(String[] args) {

    LinkedList<Integer> list = new LinkedList<>();
    list.add(1);
    list.add(2);
    list.add(3);
    list.add(4);
    list.add(5);
    list.add(6);
    list.add(7);
    list.add(8);
    list.add(9);
    list.add(0);
    System.out.println("Shuffled list: "+shuffle(list));
}

public static LinkedList shuffle(LinkedList list){
    int node = 10; //just a random node
    if(list.size()<=1){
        return list;
    }
    LinkedList<Integer>list1 = new LinkedList<>();
    LinkedList<Integer>list2 = new LinkedList<>();

    while(!list.isEmpty()){
        list1.add((Integer) list.removeFirst());
        if(!list.isEmpty()){
            list2.add((Integer) list.removeFirst());
        }
    }
    shuffle(list1);
    shuffle(list2);

    if(list2.size() < list1.size()){
        int i = (int)(Math.random() * list2.size());
        list2.set(i, node);
    }

    while(!list1.isEmpty()&&!list2.isEmpty()){
        int rand = (int)(Math.round(Math.random()));
        if(rand == 1){
            list.add(list1.removeFirst());
        }
        else if(rand == 0){
            list.add(list2.removeFirst());
        }
    }
    //If any of list1 or list2 are still empty add everything to list
    if(!list1.isEmpty()){
        list.add(list2.clone());
    }
    if(!list2.isEmpty()){
        list.add(list1.clone());
    }
    list.remove(node);
    return list;
}

}

错误如下:

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 10, Size: 2
at java.util.LinkedList.checkElementIndex(LinkedList.java:553)
at java.util.LinkedList.remove(LinkedList.java:523)
at kth.id2010.lab.lab03.Q02.Q02.shuffle(Q02.java:62)
at kth.id2010.lab.lab03.Q02.Q02.shuffle(Q02.java:39)
at kth.id2010.lab.lab03.Q02.Q02.shuffle(Q02.java:39)
at kth.id2010.lab.lab03.Q02.Q02.shuffle(Q02.java:39)
at kth.id2010.lab.lab03.Q02.Q02.main(Q02.java:22)

Answer 1

如果您收到ArrayIndexOutOfBoundsException，则意味着您正在尝试使用无效索引访问LinkedList 中的项目。例如，如果您的 LinkedList 有 10 项，则 listOfSize10.set(10, node) 将引发 ArrayIndexOutOfBoundsException.

您看到的错误很可能源于这些行:

int i = (int)(Math.random() * list2.size());
list2.set(i, node);

你能保证i总是大于或等于0并且小于list2.size()吗？

更新 查看堆栈跟踪后，错误似乎来自这些行:

int node = 10; //just a random node
list.remove(node);

这里，当列表中只有 10 项时，您显然试图删除索引 10 处的项(或第十一项)。所以你的数组索引超出了范围。