柯泽钊

上周五要实现从300万个手机号码中随机提取不重复的30万个号码，写了一个程序，跑了二三十分钟才得到结果，还不能动电脑，一动程序就未响应了，晕死，今天重新上班，觉得应该能改进的，最后终于想到了一个方法，几秒就搞定了，记下来。
因为要取随机数，而随机数可能有重复，那就必须与之前的随机数比较，若有相同的就要重新产生，这样越到后面要重新产生的几率就越高，感觉不好，这种方法就不用了。
另一种方法是生成一个链表，每个号码放到一个节点里，生成随机数取，每取到一个号码就删除相应的节点，这样就不用担心随机数重复了，因为每次号码没有与取过的重复的。
但是如果按普通的一个一个得到指定的节点，然后删除，在如此庞大的基数面前，后果是相当的可怕，所以我今天想到了再加一个数组进行配合，在一定节点之间放一个基点。
具体思路：
    取出号码，生成链表，对链表的访问需要一个节点位置，我假设生成的是单向链表L，那就只能向后一个个访问，这个过程才是最耗费时间的，为了减少这个距离，我再分配一个数组A，数组的每个元素都指向链表中的一个节点，假设为每个数组元素都指向1000个节点开头，即A[0]->Next即为第1个节点，A[1]->Next为第999个节点，如此类推。生成一个0 ~ n之间的随机数，假设为3510，则我需要的节点在第3000个节点后面，而这第3000个节点我已经存放到了A[2]->Next里，这样，我就不需要从第1个节点开始遍历链表了，节约了大量时间。用两个节点指针，pBaseNode得到基节点A[2]，pNode去得到第3510个节点，找到后，pBaseNode->Next = pNode->Next，即把pNode从链表中去掉了，使用完pNode后，删除它，释放掉内存，当然，也可以把它链接到其它链表中，以后处理。因为要保证数组A中的每个元素对应的是位置，即A[1]总是对应的第999个节点，A[2]总是对应的第1999个节点...，所以第3510个节点被去掉后，A[2]后面的数组元素所指向的节点位置都向前移动了一位，故还要把A[2]之后的数组元素所指向的节点都改为原来的后面那个节点：A[i] = A[i]->Next，当然，这样做先得保证A[i]不为NULL，不然就是程序错误而退出了。因为链表长度由n变成了n-1，所以第二次生成的随机数就只生成0 ~ n-1之间的，之后就重复操作，直到取出指定数量的号码。OK，基本思路就是这样了。