-1 
int getnum50()
{ 
  Random rand = new Random(); 
  return (1+rand.nextInt(50)); 
}
  • 您将获得一个名为的预定义函数getnum50()，该函数返回一个整数，该整数是 1-50 之间的一个随机数。
  • 您可以根据需要多次调用此函数，但请注意此函数非常耗费资源。
  • 您不能使用任何其他随机生成器。您不能更改getnum50().

以随机顺序打印数字 1-100。（不是 100 个随机数）

笔记：

  • 一世。每个数字都应该只打印一次。
  • ii. 数字列表中不应有任何模式。列表应该是完全随机的，即所有数字在任何地方出现的概率都是相等的。
  • iii. 您可以调用 getnum50() 任意次数来获取从 1 到 50 的随机数，但请尝试优化代码。
  • iv. 您不能使用除 getnum50() 之外的任何其他随机生成器函数。

我写了一些显示正确输出的代码。

import java.util.Random;

public class RandomInteger{

    int number[]=new int[100];//To store numbers in random order

    public RandomInteger(){
        int n[]=new int[100];//array to store which random numbers are generated
        int off[]={-1,0};//offset to add
        System.out.println("Length of array number100 is:"+number.length);
        System.out.println("Generating  random numbers in the range 1-100:");
        for(int n1=0;n1<number.length;n1++){
            int rnd=off[(getnum50()-1)/50]+(getnum50()*2);
            if(n[rnd-1] == 0){
                n[rnd-1]=1;//to indicate which random number is generated
                number[n1]=rnd;
                System.out.println(number[n1]+" ");
            }
        }
    }
    //end of constructor

    int getnum50(){  
        Random rand = new Random(); 
        return (1+rand.nextInt(50));      
    }

    public static void main(String args[]){
        RandomInteger m= new RandomInteger();
    }
    //end of main()
}
//end of class

虽然在该轮中被接受，但在下一轮中，面试官告诉我这getnum50()是一种昂贵的方法，即使在最好的情况下，我也必须为每个生成的数字调用两次。即 1-100 次 200 次。在最坏的情况下，它将是无穷大，平均情况下是数万。他要求我优化代码，以显着改善平均情况。我无法回答。所以请给我正确的答案？我将如何优化我上面的代码？

4

5 回答 5

2

One stupid optimization would be be to just realize that since your randomized source is limited to 1-50, you might as well set TWO array positions, e.g.

rand = getnum50();
n[rand] = 1;
n[rand+50] = 1;

Now the array will be slightly "less" random, because every index n is going simply be 1/2 of whatever's at n+50, but at least you've cut ~half the build array construction time.

于 2013-07-19T18:36:54.210 回答
2

我认为他们希望你产生一个洗牌算法。

在此，您从一个正好包含 100 个数字的数组（从 1 到 100 的顺序）开始，然后在每次迭代中对数字进行洗牌。

做足够多的次数，原始数组是完全随机的。

于 2013-07-19T18:53:04.787 回答
0

您两次调用方法 getnum50() 的原因是因为这一行：

int rnd = off[(getnum50()-1)/50] + (getnum50()*2);

这似乎是不言自明的。而你最坏的情况如此糟糕的原因是因为这个块：

if(n[rnd - 1] == 0){
    n[rnd - 1] = 1;          //to indicate which random number is generated
    number[n1] = rnd;
    System.out.println(number[n1] + " ");
}

根据您的运气有多糟糕，获得每个值可能需要很长时间。因此，最好的情况是，您进行两次 getnum50() 调用，这将是第一次发生，但是当您填满数组时，它变得越来越不可能。对于 100 个号码，最后一个号码第一次有 1% 的机会成功，每次失败时，您再调用两次 getnum50()。

抱歉，这并不能回答如何提高您的效率，但它确实解释了效率问题的原因。希望能帮助到你。

于 2013-07-19T18:56:06.043 回答
0

您的问题是，如果您在列表的末尾，您将不得不生成大量随机数才能在剩下的几个位置中获得一个数字。您可以减少几种适合您当前答案的方法，如下所示：

  while(n[rnd-1] == 1)
  {
    rnd++;
    rnd=end%101;
  }
  n[rnd-1]=1;//to indicate which random number is generated
  number[n1]=rnd;
  System.out.println(number[n1]+" ");

但是，如果您假设 getnum50 比您可以编写的任何东西都贵，您可以减少您在填写列表后半部分时调用的 getnum50 的数量。每次找到一个数字时，您都可以将搜索空间减少一个（使用非原语）：

while(myArrayList.size()>1)
{
   int rnd=0;
   if(myArrayList.size()>50);
     rnd=((getnum50()-1)/50)+((getnum50()*2)%myArrayList.size())+1;
   else
     rnd=getnum50()%myArrayList.size()+1;
   System.out.println(rnd);
   myArrayList.remove(rnd);
}
System.out.println(myArrayList.get(rnd);
myArrayList.remove(rnd);

在此示例中，您的最佳、平均和最差是 149 个 getnum50 调用；

于 2013-07-19T18:58:02.380 回答
0

50 是红鲱鱼。使用两次调用 random50，mod 10。现在你有两个数字：十位和个位。这为您提供了一个 random100() 函数。

真正的杀手是生成和检查方法。相反，将数字 1-100 放入数组列表中，并使用您的 random100 删除随机索引。现在，您最坏的情况有 2n 次调用 random50。还有一些问题需要解决 - 超支 - 但这是我要研究的方法。

于 2013-07-19T18:53:40.080 回答