题目:给你一个长度为N的链表。N很大,但你不知道N有多大。你的任务是从这N个元素中随机取出k个元素。你只能遍历这个链表一次。你的算法必须保证取出的元素恰好有k个,且它们是完全随机的(出现概率均等)。
解答:
题其实是编程珠玑习题12.10的推广,原题既是k=1的情况,关键就是想到可以替换以前已经选择的元素。
按照这个思路:
1. 对于前k个,全部选择,即选择集S里为前k个元素
2. 第k+i(i>0)个时,令r1=rand(1,k+i),如果r1>k,则保持现有的选择集合S不变
3. 如果r1<=k, 令r2=rand(1,k),并让第k+i元素(即当前元素)替换集合S里第r2个元素
归纳:
1. 如果N=k, 前k个全部选择,被选择概率p=1
2. 如果N=k+1, 第k+1个被选择的概率为p=k/(k+1),前k个被选择的概率为
p=1*(1/(k+1)+(k/(k+1))*((k-1)/k)) = k/(k+1)
3. 如果N=k+i,第k+i个被选择的概率为p=k/(k+i)=k/N,前k+i-1(N-1)个被选择的概率为
p=k/(k+i-1) * (i/(k+i) + (k/(k+i) * (k-1)/k) = k/(k+i-1) * (i/(k+i) +
(k-1)/(k+i)) =
k/(k+i-1) * (k+i-1)/(k+i) = k/(k+i) = k/N
分享到:
相关推荐
以N-长链烷基脒为原料,在CO2氛围下制备得到N-长链烷基脒基碳酸氢盐。系统研究其表面活性发现:N-长链烷基脒基碳酸氢盐具有很好的表面活性,γcmc在20.5~32.3 mN/m之间;随着疏水链长的增加,N-长链烷基甲脒碳酸氢盐和N-...
长链n-3多不饱和脂肪酸EPA和DHA对肠道上皮细胞乳糜微粒及甘油三脂的影响,郑培培,徐俊科,本试验研究了不同饱和度、不同浓度的长链脂肪酸对肠道上皮细胞Caco-2乳糜微粒(CM)的分泌、甘油三酯(TG)的重新合成和分泌的...
标题中的“电子功用-含二-(对-(N,N,N-十二烷基二甲氨基溴化铵)苯甲醛)缩肼电解液及其制备方法”揭示了一个与电子技术相关的重要知识点,涉及到一种特殊的电解液及其制备工艺。电解液在电子设备,特别是电池系统...
N-myc转录调控长链非编码RNA-ncRAN的作用机制研究,于萌,朱育焱,目的 利用生物信息学和分子生物学方法揭示在神经母细胞瘤中转录因子N-myc调控长链非编码RNA-ncRAN的机制。方法 通过内源性沉默或可控�
【长链非编码RNA在肝癌中的功能和机制研究】\n\n长链非编码RNA(Long non-coding RNA, lncRNA)是一类长度超过200个核苷酸的非编码RNA分子,虽然不编码蛋白质,但在细胞内扮演着重要的调控角色。近年来,随着科学...
《音视频-编解码-长链非编码RNASRHC在肝癌中的表达和功能》这篇文献主要探讨了长链非编码RNA (lncRNA) SRHC在肝癌发生发展中的作用及其临床意义。lncRNA是一类长度超过200个核苷酸但不编码蛋白质的RNA分子,近年来在...
6. **DNA甲基化**:DNA甲基化是表观遗传修饰的一种,可以影响基因的表达,可能导致基因沉默。在乳腺癌中,MALAT1的甲基化可能与其表达水平的变化相关。 7. **统计分析**:实验数据通过SPSS软件进行统计处理,以确定...
然而,这篇名为"音视频-编解码-长链非编码RNAMALAT1在胰腺导管腺癌中的表达及功能研究"的论文却将这一技术与医学研究结合在一起,探讨了生物学领域的前沿问题。 【长链非编码RNA (lncRNA) MALAT1在胰腺导管腺癌中的...
在这个"服务器推送示例 - 支持IE、FF、谷歌 - 长链防断版"中,我们将探讨如何实现跨浏览器的服务器推送,并解决长连接防止断连的问题。 1. **服务器推送技术**:服务器推送主要基于HTTP/2和WebSocket协议。HTTP/2的...
【音视频编解码】- 长链非编码RNA在生物医学领域的研究 这篇文档虽然标题提及"音视频-编解码",但实际内容并非关于音视频处理技术,而是涉及生物医学研究,特别是分子生物学领域的一个特定研究。长链非编码RNA ...
【标题】和【描述】提及的是一个关于音视频编解码的学术研究,但实际上内容却涉及生物医学领域,特别是关于长链非编码RNA (lncRNA) ZXF2在肺腺癌中的作用。因此,这里并没有提及任何与音视频编解码相关的信息,而是...
TUG1(牛磺酸上调基因1)和GAS5(生长停滞特异性5)是两种具有表观遗传调控功能的lncRNA,它们可能通过影响基因表达来参与细胞的生理和病理过程。 本研究的主要目标是探讨这两种lncRNA在结直肠癌组织与正常组织中的...
标题和描述中提到的"音视频-编解码"与实际文档内容不符,因为文档主要研究的是长链非编码RNA (lncRNA) MALAT1在胰腺导管腺癌中的表达和功能,而非音视频处理或编解码技术。因此,我们将重点放在lncRNA的相关知识上。...
【音视频编解码技术与长链非编码RNA在疾病研究中的应用】 音视频编解码技术是信息技术领域中一个重要的组成部分,它涉及到音频和视频...关键词:长链非编码RNA,系膜增生性肾小球肾炎,表观遗传调控,转录,微阵列芯片
长链非编码RNA(lncRNA)ZXF2在这个领域的发现和影响是论文的核心。 长链非编码RNA ZXF2是一种在生物体内不直接参与蛋白质合成的RNA分子,但它们在基因调控和疾病发展中起着重要作用。在肺腺癌中,ZXF2被发现具有高...
【长链非编码RNA BANCR】: 长链非编码RNA (lncRNA) 是一类不编码蛋白质但参与多种生物学过程的RNA分子。BRAF激活的长链非编码RNA (BANCR) 在该研究中被关注,因为它在黑色素瘤中被发现高表达,并与细胞迁移有关。在...
【长链非编码RNA(lncRNA)MEG3】是主要研究对象。lncRNA是一类长度超过200个核苷酸、但不编码蛋白质的RNA分子。MEG3(Maternally Expressed Gene 3)是lncRNA的一种,它在多种生物学过程中发挥作用,包括基因表达...
【长链非编码RNA】(lncRNA)是近年来生物医学研究中的热点,它是一类长度超过200个核苷酸(nt)的非编码RNA分子,不编码蛋白质,但参与多种生物学过程,如基因调控、染色质修饰、信号传导等。在本文中,lncRNA与青...
【标题】和【描述】提及的是关于音视频编解码领域的研究,但核心内容实际聚焦于生物学领域,尤其是病理学与病理生理学的博士研究,主题是长链非编码RNA (lncRNA) Inc-LEMGC对胃癌侵润和转移的调控作用及相关机制。...
标题和描述中提到的文件主要关注的是长链非编码RNA(LncRNA)PTENP1在肾透明细胞癌(Renal Clear Cell Carcinoma,RCCC)中的功能及分子机制研究。LncRNA是一种长度超过200个核苷酸的非编码RNA分子,虽然不编码...