【简单】从N个数中等概率打印M个数－Java

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请轻击人工智能教程大家好！欢迎来到我的网站！ 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑，人工智能时代就要来临了，科… 继续阅读 前言https://www.captainai.net/troubleshooter

package live.every.day.ProgrammingDesign.CodingInterviewGuide.Other; /** * 从N个数中等概率打印M个数 * * 【题目】 * 给定一个长度为N且没有重复元素的数组arr和一个整数n，实现函数等概率随机打印arr中的M个数。 * * 【要求】 * 1.相同的数不要重复打印。 * 2.时间复杂度为O(M)，额外空间复杂度为O(1)。 * 3.可以改变arr数组。 * * 【难度】 * 简单 * * 【解答】 * 如果没有空间复杂度的限制，可以用哈希表标记一个数之前是否被打印过，就可以做到不重复打印。解法的关键点是利用要求3改变数 * 组arr。打印过程如下： * 1.在[0,N-1]中随机得到一个位置a，然后打印arr[a]。 * 2.把arr[a]和arr[N-1]交换。 * 3.在[0.N-2]中随机得到一个位置b，然后打印arr[b]，因为打印过的arr[a]已被换到了N-1位置，所以这次打印不可能再次出现。 * 4.把arr[b]和arr[N-2]交换。 * 5.在[0,N-3]中随机得到一个位置c，然后打印arr[c]，因为打印过的arr[a]和arr[b]已被换到了N-1位置和N-2位置，所以这次 * 打印都不可能再出现。 * 6.依此类推，直到打印M个数。 * 总之，就是把随机选出来的数打印出来，然后将打印的数交换到范围中的最后位置，再把范围缩小，使得被打印的数下次不可能再被选 * 中，直到打印结束。很多有关等概率随机的面试题都是用这种和最后一个位置交换的解法，希望这种小技巧能引起读者的重视。具体过 * 程请参看如下代码中的printRandM方法。 * * @author Created by LiveEveryDay */ public class FromNNumbersEquiprobabilityPrintMNumbers<K, V> { public static void printRandM(int[] a, int m) { if (a == null || a.length == 0 || m < 0) { return; } m = Math.min(a.length, m); int count = 0; int i = 0; while (count < m) { i = (int) (Math.random() * (a.length - count)); System.out.printf("%d ", a[i]); swap(a, a.length - count++ - 1, i); } } private static void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; } public static void main(String[] args) { int[] a = {1, 4, 6, 7, 3, 9, 2, 8, 5, 0}; printRandM(a, 8); } } // ------ Output ------ /* 1 3 5 0 7 8 2 9 */