java – 从1-50的生成器生成1-100的随机数
在最近的一次采访中,我被问到以下问题:
我想出了以下代码,它给出了正确的输出. import java.util.Random; public class Test { public static void main(String[] args) { int[] rs = new int[100]; int count = 0; int k; while (count != 100) { // I decided to simply multiply the result of `getrnd50()` by 2. // But since that would generate only even numbers,k = getrnd50() * 2; // I decided to randomly subtract 1 from the numbers. // Which i accomlished as follows. if (getrnd50() <= 25) // 25 is to half the possibilities. k--; // Every number is to be stored in its own unique location // in the array `rs`,the location is `(number-1)`. // Every time a number is generated it is checked whether it has // already been generated. If not,it is saved in its position,printed and // `count` is incremented. if (rs[k-1] == 0) { rs[k-1] = k; count++; System.out.print(k + " "); } } } // This is the method and i am not supposed to touch it. static int getrnd50() { Random rand = new Random(); return (1 + rand.nextInt(50)); } } 虽然它在那一轮被接受,但在下一轮中,面试官告诉我getrnd50()是一种昂贵的方法,即使在最好的情况下,我必须为每个生成的数字调用它两次.即1-100的200次.在最坏的情况下,它将是无限的,平均情况下数万.他要求我优化代码,以便显着改善平均情况. 当我表示无法做到时,他给了我一个暗示,他说:
虽然我理解他的漂移我不知道它会如何帮助我,所以显然我被拒绝了.现在我很想知道答案.帮我! Thanx提前! 注意:如果有人懒得写一个冗长的代码只是指出数字生成部分,其余的很容易.此外,我们不一定遵循提示. 解决方法
关键是不检查你之前是否已经生成了这个数字,当只查找剩余数字时会变得非常昂贵,但要按顺序生成数字1-100,然后进行随机播放.
在您的代码中,当您生成100个数字中的99个时,您将循环生成随机数,直到找到剩余的1个数字.这就是为什么你的版本中的平均情况如此糟糕. 相反,如果您只是随机播放一个数组,您只需要拥有与随机数一样多的随机数,并且只需要与您需要数字输出一样多的随机操作. (有关改组的详细信息,请查看Fisher-Yates shuffle,特别是可以生成混洗数组的内向外变体) 要生成随机数,您需要一个变量生成器,而不是固定的1-50.您可以通过各种方式处理此问题,但如果您真的希望输出在可能的状态中具有良好的分布,则要非常小心地将偏差引入结果中. 例如,我建议使用整数位,并使用移位,而不是尝试使用模数.如果值超出所需范围,这确实涉及一定量的循环,但是如果不能修改原始随机数生成,则您的手有点束缚. static int bits = 0; static int r100 = 0; static int randomInt(int range) { int ret; int bitsneeded = 32 - Integer.numberOfLeadingZeros(range - 1); do { while(bits < bitsneeded) { int r = (getrnd50()-1) * 50 + getrnd50()-1; if(r < 2048) { r100 <<= 11; r100 |= r; bits += 11; } } ret = r100 & ((1 << bitsneeded) - 1); bits -= bitsneeded; r100 >>= bitsneeded; } while(ret >= range); return ret + 1; } 这个实现将使用150个随机数区域中的某个值为您的100个值混洗数组.这比模数版本更差,但优于输入范围的2倍,这是原始版本的最佳情况.如果随机生成是真正随机的,那么仍然是无穷大的最坏情况,但随机生成通常不会那样工作.如果确实如此,我不确定在给定约束的情况下,未经证实的结果是否真实. 为了说明,由于结果很微妙,这里是我建议的随机例程与模数版本的关系图: 总而言之,我认为虽然你的随机生成效率有点低,并且可以得到改善,但是面试官正在寻找的真正大赢家,首先不需要这么多随机数,通过洗牌而不是以不断下降的概率重复搜索. (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |