[算法]几个有趣的关于数列的O(1)空间O(n)时间小算法

1 数列L中有n个整数。其中有k个数字出现了两次，1个数字出现了一次(所以n=2k+1)。找出只出现一次的那个数字。
解： 将n个数字xor以后，重复出现的就会消失。剩下的就是只出现一次的。

2 数列L中有n个数。已知其中有一个数字出现了至少 n/2+1次。找出这个数字。
解： 用链表存储这n个数字。p指向当前考察的数字。p从链表头开始。如果p和p->next的数字相同，p=p->next，如果不同，则将p和p->next一同从链表中删除。当p->next是链表尾的时候，p就是所求数字。

3 数列L中有n=2k个数字a1,a2,...,an,b1,b2,...,bn。将其变换为a1,b1,a2,b2,...,an,bn。可以将这个问题理解为扑克里的洗牌。
解： 很难的题目。这里有一篇论文http://webhome.cs.uvic.ca/~jellis/perfect.html。