腾讯BT的面试题

import java.util.Random;

public class JustForTest
{
	// 随机数的最大值
	private static int MAX_RANDOM_VALUE = 5 * 7 * 8 * 9;
	// 钻石的个数
	private static int DIAMOND_COUNT = 10;

	private static Random RANDOM = new Random();

	public static void main(String[] args)
	{
		// 循环的次数
		int count = 1000000;
		// i表示到第几层后才去取
		for (int i = -1; i < DIAMOND_COUNT - 1; i++)
		{
			// 得到最大的次数
			int trueGet = 0;
			for (int j = 0; j < count; j++)
			{
				int[] randomDiamonds = generateRandomNumbers();
				int index = getMaxNumber(randomDiamonds, i);
				// 如果是最大的，则取到了
				if (randomDiamonds[index] == DIAMOND_COUNT - 1)
				{
					trueGet++;
				}
			}
			// 计算得到最大的比例
			float percent = (float) trueGet / count;
			System.out.println("m=" + (i + 1) + ", p=" + percent);
		}
	}

	// 生成0到9的随机字符窜数组
	private static int[] generateRandomNumbers()
	{
		boolean[] hasUsed = new boolean[DIAMOND_COUNT];
		int[] randomNumbers = new int[DIAMOND_COUNT];
		for (int i = 0; i < DIAMOND_COUNT; i++)
		{
			// 得到随机钻石的大小
			int size = RANDOM.nextInt(MAX_RANDOM_VALUE) % DIAMOND_COUNT;
			while (hasUsed[size])
			{
				size = (size + 1) % DIAMOND_COUNT;
			}
			randomNumbers[i] = size;
			hasUsed[size] = true;
		}
		return randomNumbers;
	}

	private static int getMaxNumber(int[] numbers, int m)
	{
		int maxSize = -1;
		// 取m层中最大的
		for (int i = 0; i <= m; i++)
		{
			if (numbers[i] > maxSize)
			{
				maxSize = numbers[i];
			}
		}
		// 从m+1层开始取比maxSize还大的
		for (int i = m + 1; i < numbers.length; i++)
		{
			// 如果比maxSize还大，则出电梯
			if (numbers[i] > maxSize)
			{
				return i;
			}
		}
		// 如果没有取到，则取最后一个
		return numbers.length - 1;
	}
}