1

我很难为改组算法使用伪代码并将其转换为有效的 Java 代码。我正在尝试对链表进行洗牌。总的来说，该方法获取链表头的指针，并随机返回指向同一个链表头的指针。我想使用我创建的 getLength 和 getItem 方法。

public static ListElement shuffle(ListElement head){
  head = head.getLength();
  ListElement head2= null;
  while( head == null) {
    int random = (int) Math.random() *  n;
    for(int i=0;i<random;i++){
        head= head.getNext();
    }
  }
  return head;    
}

伪代码：

A list L of length n
A new list R, empty
while L is not empty
   pick a random k 
   such that 0<=k<= (length L)
   remove the kth element of L
      call it e
   prepend e to R
4

3 回答 3

0 
head = head.getLength();

看起来应该是int n = head.getLength();

while( head == null) {

看起来应该是while (head != null) {

int random = (int) Math.random() *  n;
for(int i=0;i<random;i++){
    head= head.getNext();

您正在覆盖 head 变量。您需要使用一个新变量来查找列表的第 k 个元素，并让 head 指向旧列表。

找到元素后，您还没有对元素执行任何操作，您需要从旧列表（硬）中提取它并将其添加到新列表中。

return head;

您需要返回新列表。

于 2012-07-12T00:06:48.830 回答
0

我只是稍微重写了代码，使其遵循伪代码。

ListElement head2 = null;
int length = head.getLength();

while (head != null) {
    int k = (int) Math.random() * length;

    // Assume there is function deleteAt(index) that removes
    // the element at specified index and returns the deleted
    // element
    ListElement e = head.deleteAt(k);
    // Although I can just give the implementation - I'll leave this
    // as exercise.

    // You can have a function that add element to front
    // head2.addFront(e);
    e.setNext(head2);
    head2 = e;

    // Instead of querying the length again
    // decrement the length
    length--;
}
return head;
于 2012-07-12T00:08:59.430 回答
0

您的伪代码的问题在于，最坏的情况是，每次您想要删除一个元素以将其添加到新列表时，您都必须迭代到原始列表的末尾。

原始列表 o = [a,b,c,d,e,f,g]
新列表：n = []

o = [a,b,c,d,e,f]
n = [g]

o = [a,b,c,d,e]
n = [g,f]

o = [a,b,c,d]
n = [g,f,e]

...

我现在能想到的最佳性能答案是创建一个列表大小的数组并遍历原始链表，将元素插入到随机位置的数组中：

原始列表 o = [a,b,c,d,e,f,g]
新数组 a = [,,,,,,]

o = [b,c,d,e,f,g]
a = [,,a,,,,]

o = [c,d,e,f,g]
a = [,,a,,b,,]

o = [d,e,f,g]
a = [c,,a,,b,,]

o = [e,f,g]
a = [c,,a,,b,d,]

...

将它们放入数组后，循环遍历数组并修复链接。

在原始版本中，您必须调用getNext()6 次，然后 5 次，然后 4 次，然后 3 次......

在我的情况下，您调用getNext()了 6 次，然后循环通过数组重置您的“下一个”引用。

于 2012-07-12T00:14:13.827 回答