我必须随机排列长度为 n 的单链表的 N 个第一个元素。每个元素定义为:
typedef struct E_s
{
struct E_s *next;
}E_t;
我有一个根元素,我可以遍历整个大小为 n 的链表。随机排列仅 N 个第一个元素(从根开始)的最有效技术是什么?
所以,给定 a->b->c->d->e->f->...x->y->z 我需要做点什么。比如 f->a->e->c->b->...x->y->z
我的具体情况:
- n-N 大约是 n 的 20%
- 我的 RAM 资源有限,最好的算法应该到位
- 我必须在循环中进行多次迭代,所以速度确实很重要
- 不需要理想的随机性(均匀分布),“几乎”随机就可以
- 在进行排列之前,我已经遍历了 N 个元素(用于其他需要),所以也许我也可以将其用于排列
更新:我找到了 this paper .它指出它提出了一种 O(log n) 堆栈空间和预期 O(n log n) 时间的算法。
最佳答案
我没试过,但你可以使用“随机 merge-sort”。
更准确地说,您将 merge
例程随机化。您没有系统地合并两个子列表,而是基于抛硬币来进行合并(即以 0.5 的概率选择第一个子列表的第一个元素,以 0.5 的概率选择正确的子列表的第一个元素)。
这应该在 O(n log n)
中运行并使用 O(1)
空间(如果正确实现)。
您可以在下面找到一个 C 中的示例实现,您可以根据自己的需要进行调整。请注意,此实现在两个地方使用随机化:在 splitList
和 merge
中。但是,您可以只选择这两个地方之一。我不确定分布是否是随机的(我几乎可以肯定它不是),但一些测试用例产生了不错的结果。
#include <stdio.h>
#include <stdlib.h>
#define N 40
typedef struct _node{
int value;
struct _node *next;
} node;
void splitList(node *x, node **leftList, node **rightList){
int lr=0; // left-right-list-indicator
*leftList = 0;
*rightList = 0;
while (x){
node *xx = x->next;
lr=rand()%2;
if (lr==0){
x->next = *leftList;
*leftList = x;
}
else {
x->next = *rightList;
*rightList = x;
}
x=xx;
lr=(lr+1)%2;
}
}
void merge(node *left, node *right, node **result){
*result = 0;
while (left || right){
if (!left){
node *xx = right;
while (right->next){
right = right->next;
}
right->next = *result;
*result = xx;
return;
}
if (!right){
node *xx = left;
while (left->next){
left = left->next;
}
left->next = *result;
*result = xx;
return;
}
if (rand()%2==0){
node *xx = right->next;
right->next = *result;
*result = right;
right = xx;
}
else {
node *xx = left->next;
left->next = *result;
*result = left;
left = xx;
}
}
}
void mergeRandomize(node **x){
if ((!*x) || !(*x)->next){
return;
}
node *left;
node *right;
splitList(*x, &left, &right);
mergeRandomize(&left);
mergeRandomize(&right);
merge(left, right, &*x);
}
int main(int argc, char *argv[]) {
srand(time(NULL));
printf("Original Linked List\n");
int i;
node *x = (node*)malloc(sizeof(node));;
node *root=x;
x->value=0;
for(i=1; i<N; ++i){
node *xx;
xx = (node*)malloc(sizeof(node));
xx->value=i;
xx->next=0;
x->next = xx;
x = xx;
}
x=root;
do {
printf ("%d, ", x->value);
x=x->next;
} while (x);
x = root;
node *left, *right;
mergeRandomize(&x);
if (!x){
printf ("Error.\n");
return -1;
}
printf ("\nNow randomized:\n");
do {
printf ("%d, ", x->value);
x=x->next;
} while (x);
printf ("\n");
return 0;
}
关于c++ - 随机排列单链表的前 N 个元素,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4421639/