Hard 随机选择subset @CareerCup
选择 随机 Hard CareerCup
2023-09-11 14:20:12 时间
算法同上题
package Hard; import CtCILibrary.AssortedMethods; /** * Write a method to randomly generate a set of m integers from an array of size n. Each element must have equal probability of being chosen. 译文: 写一个函数,随机地从大小为n的数组中选取m个整数。要求每个元素被选中的概率相等。 * */ public class S18_3 { /* Random number between lower and higher, inclusive */ public static int rand(int lower, int higher) { return lower + (int)(Math.random() * (higher - lower + 1)); } public static void swap(int[] a, int n, int m){ int tmp = a[n]; a[n] = a[m]; a[m] = tmp; } /* pick M elements from original array, using only elements 0 through i (inclusive).*/ public static int[] pickMRecursively(int[] original, int m, int i) { if (i + 1 < m) { // Not enough elements return null; } else if (i + 1 == m) { // Base case -- copy first m elements into array int[] set = new int[m]; for (int k = 0; k < m; k++) { set[k] = original[k]; } return set; } else { int[] set = pickMRecursively(original, m, i - 1); int k = rand(0, i); if (k < m) { set[k] = original[i]; } return set; } } /* pick M elements from original array. Clone original array so that * we don’t destroy the input. */ public static int[] pickMRandomly(int[] original, int m) { for (int i = 0; i < m; i++) { int k = rand(i, original.length-1); // 产生i到n-1间的随机数 swap(original, i, k); } int[] subset = new int[m]; for(int i=0; i<m; i++){ subset[i] = original[i]; } return subset; } public static void main(String[] args) { int[] cards = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; System.out.println(AssortedMethods.arrayToString(cards)); int[] set = pickMRandomly(cards, 4); System.out.println(AssortedMethods.arrayToString(set)); } }
相关文章
- Java实现选择排序和冒泡排序
- 如何设置select下拉禁止选择
- 《从零开始学Swift》学习笔记(Day 30)——选择类还是结构体呢?
- [GPT] 序列模型分类及其模型方案选择
- Atitit order algo 排序算法 算法之道 目录 1.1. 生活中常用的排序是插入排序和选择排序2 2. 0.1 算法分类2 3. .2 算法复杂度3 4. 十大经典排序算法(动图
- LVS、Nginx、HAproxy有什么区别?工作中你怎么选择?
- 使用带外空间信息选择毫米波波束(Matlab代码实现)
- 数字彩色图像的水印嵌入仿真,带GUI界面,可以选择图片和水印,可以选择不同的攻击方式验证水印的鲁棒性
- 笔记:电阻的选择之耐压
- e813. 获得当前选择的菜单或菜单项
- 数据结构与算法之选择排序(含改进版)
- selenium下拉框选择
- 房子装修选择自装,物业办装修手续,需要哪些资料?