用数组中最后元素覆盖随机抽取到的位置的算法问题-问答-阿里云开发者社区-阿里云

用数组中最后元素覆盖随机抽取到的位置的算法问题

``````         // r是随机数，不会超界；ｎ由numbers数组的length得道
numbers[r] = numbers[n - 1];
n--;``````

code:

``````import java.util.*;
/**
* This program demonstrates array manipulation.
* @version 1.20 2004-02-10
* @author Cay Horstmann
*/
public class LotteryDrawing
{
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);

System.out.print("How many numbers do you need to draw? ");
int k = in.nextInt();

System.out.print("What is the highest number you can draw? ");
int n = in.nextInt();

// fill an array with numbers 1 2 3 . . . n
int[] numbers = new int[n];
for (int i = 0; i < numbers.length; i++)
numbers[i] = i + 1;

// draw k numbers and put them into a second array
int[] result = new int[k];
for (int i = 0; i < result.length; i++)
{
// make a random index between 0 and n - 1
int r = (int) (Math.random() * n);

// pick the element at the random location
result[i] = numbers[r];

// move the last element into the random location
numbers[r] = numbers[n - 1];
n--;
}

// print the sorted array
Arrays.sort(result);
System.out.println("Bet the following combination. It'll make you rich!");
for (int r : result)
System.out.println(r);
}
}``````

1 条回答

• 我说我不帅他们就打我，还说我虚伪

这是一个数组内部取随机值后换位置的算法,每次取数组中的随机数后,把这个随机数与数组尾部的值换位,这样取过的值全部移动到数组尾部,而新的随机值会在0和n-1之间,也就是从头部到最后一个未换位的位置之间取,因此不会有重复值出现.
比如:
numbers = [0,1,2,3,4,5],
假如r=2,则取出一个随机值numbers[2] ,也就是数字2,
然后进行换位,numbers[r] = numbers[n - 1],2被换到数组最后一位,数组此时变成:
[0,1,5,3,4,2],
此时5换到了前面,这时n--后,再次取随机值时是从[0,1,5,3,4,2]中取了(加粗部分),所以新的随机值必定不会包含已经取出的2.
同理,再次取值时,这个值会放到倒数第二位.

2019-07-17 18:54:02
赞同 展开评论 打赏

89
1
0
109
1
0
488
1
0
432
1
0
1180
1
0
935
1
0
1000
1
0
470
1
0
236
0
0
3254
3
0