在阵列考虑重复存储随机值 [英] storing random values in arrays considering duplicates
问题描述
本的<一个新版本href="http://stackoverflow.com/questions/4990164/estimating-the-probability-of-3-people-sharing-a-birthday">this帖子为了隔离从概率问题的编程问题
This a new version of this post in order to isolate the programming question from the probability question.
我要存储一些如25，随机在一个阵列产生1和365之间的数字。但我需要跟踪重复的。下面是我在想这样做的：
I want to store a number of e.g. 25 randomly generated numbers between 1 and 365 in an array. But i need to keep track of duplicates. Here's how i was thinking of doing it:
-
创建4个数组：一个主数组，数组2的重复，阵列3的重复和一个超过3重复
create 4 arrays: a master array, an array for 2 duplicates, an array for 3 duplicates and one for more than 3 duplicates
逐个添加每个生成的一把手到主阵列。但这样做，遍历数组，看它是否在那里已经之前。如果是这样，将其添加到第二阵列，但在这样做之前重复上述过程等
add each generated number one by one into the master array. But before doing so, loop through the array to see if it's in there already. If so, add it to the second array, but before doing so repeat the above process and so on
在过程结束时，我可以指望每个数组中的非空值就知道我有多少独特的数字有多少上前两次等
at the end of the process i could count the non-null values in each array to know how many unique numbers i have, how many came up twice etc
它似乎并没有成为一个非常有效的算法。任何建议，以改善它？
it doesn't seem to be a very efficient algorithm. Any suggestions to improve it?
可我建议的方法被认为是大O（N），即线性？
Can my suggested approach be considered to be Big O(n) i.e. linear?
推荐答案
下面是如何，我认为这个问题是可以解决的。
Here is how I think the problem can be solved.
- 有两个数组：一个主一个包含生日和一个含有的时候，它已经重复的号码 。
- 生成一个随机的生日。
- 循环通过主阵列，看看它是否已经存在。
- 如果它不存在，另一个阵列中它添加到主阵列和在相同的索引位置，存储1。 （如果添加了生日掌握[3]，商店1号[3]）
- 如果它已经存在，添加一个到另一个阵列中的相应指标。
- 现在，你的主数组包含其他数组中生成的生日和相应的指标将有次被重复的次数。 （主[0] [0]已的次数的时间反复进行日期和数字）。
希望这有助于。
这篇关于在阵列考虑重复存储随机值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
