范文无忧网面试笔试笔试回答

我做的google数组随机排序的算法

10月30日 编辑 fanwen51.com

[腾讯的一道笔试算法题解答]假设有这样一种字符串,它们的长度不大于 26 ,而且若一个这样的字符串其长度为 m ,则这个字符串必定由 a, b, c ... z 中的前 m 个字母构成,同时我们保证每个字母出现且仅出现一...+阅读

发信人: northor(追求理想的过程是曲折艰辛的!), 信区: Job

标 题: 我做的google数组随机排序的算法

发信站: 瀚海星云 (2006年05月30日23:44:13 星期二), 站内信件 POST

由于一开始觉得这个题目不太好做,

就放在最后做了,

结果时间不够,只写了算法:

我考虑题干强调的是一定要随机,就是越乱越好,

于是我就联想到了一堆乒乓球在笼子里摇啊摇的,抽奖的过程,

这个过程应该算是符合题目的要求吧,

那么怎么用random函数来实现这个功能呢?

我又建立了三个int型数组,b[len],c[len],d[len]

首先N = len,乒乓球的个数是N,

然后摇奖:利用random产生0到N-1的随机数,

记作b[0],d[0]=b[0];

这是摇出的第一个球的号码,然后对c[len]赋值,

这个数组,我规定它的作用是对剩下的乒乓球标记,

因为摇出了一个球,剩下了N-1个,

而随机数只能在0开始的连续整数之间产生,

所以剩下的球的号码要是连续整数就可以继续摇了,

所以c[len]记录我对乒乓球的重新标号,

如果最初乒乓球的号码小于b[0],就保持原来的号码,

等于b[0],就让号码为N(作废),

大于b[0]的,全部减1,

这样剩下的N-1个乒乓球的标号就是0到N-2了,

然后产生利用random产生0到N-2的随机数,

对标记号码摇奖,利用摇出的乒乓球的标记号码b[1],

查到它的真实号码d[1],

这样第二个随机位置d[1]就产生了,

然后再根据b[1]给剩下的N-2个乒乓球重新标记,

如果乒乓球的标记号码小于b[1],就保持原来的标记号码,

等于b[1],就让号码为N(作废),

大于b[1]不等于N的,全部减1,

大于b[1]等于N的,不变。

重新标记之后,产生0到N-3的随机数,

就产生了第三个乒乓球的随机号码b[2],

反回去查询真实号码,得到d[2];

......

最后我们得到了d[len]这个数组,

可以让c[i]=a[d[i]];

然后再把c赋给a,

这样一个模拟乒乓球摇奖的随机过程就完成了,

如果有可能,可以看到a[len]

打乱后排列的顺序,

和一个一个地摇出乒乓球号码的概率分布是一致的。

期待高手点评,

_

.

延伸阅读:

迅雷笔试算法智力上机凭印象了: 算法题: 1.连接两个单向链表,返回排序后的结果。 2.一个保存有10000个URL的文本文件,删除其中相同的URL。 3.将9个石子放在9x9的方格中,要求同行、同列、45度上无两个...

层次遍历算法笔试题层次遍历算法 二叉树的数据结构 structBinaryTree { int value; 不写模板了,暂时用整形代替节点的数据类型 BinaryTree *left; BinaryTree *right; }; BinaryTree*root; 已知...

后序遍历非递归算法后序遍历非递归算法 #define maxsize 100 typedef enum{L,R} tagtype; typedef struct { Bitree ptr; tagtype tag; }stacknode; typedef struct { stacknode Elem[maxsize]...

google数组随机排序的算法由于一开始觉得这个题目不太好做, 就放在最后做了, 结果时间不够,只写了算法: 我考虑题干强调的是一定要随机,就是越乱越好, 于是我就联想到了一堆乒乓球在笼子里摇啊摇的,...

做的google数组随机排序的算法由于一开始觉得这个题目不太好做, 就放在最后做了, 结果时间不够,只写了算法: 我考虑题干强调的是一定要随机,就是越乱越好, 于是我就联想到了一堆乒乓球在笼子里摇啊摇的,...

推荐阅读
图文推荐
栏目列表