给定n个数字，每个数字都有一定的出现频率。返回一个概率与其发生频率成正比的随机数。
null
例子：
Let following be the given numbers. arr[] = {10, 30, 20, 40} Let following be the frequencies of given numbers. freq[] = {1, 6, 2, 1} The output should be 10 with probability 1/10 30 with probability 6/10 20 with probability 2/10 40 with probability 1/10
很明显，简单的随机数生成器在这里无法工作，因为它无法跟踪发生的频率。
我们需要以某种方式将问题转化为我们已知解决方案的问题。
一种简单的方法是使用辅助数组（比如aux[]）并根据数字出现的频率复制数字。生成一个介于0和Sum-1（包括两者）之间的随机数（比如r），其中Sum表示频率数组的总和（在上面的示例中为freq[]）。返回随机数aux[r]（此方法的实现留给读者作为练习）。
上述方法的局限性在于，当发生频率较高时，会消耗大量内存。如果输入是997、8761和1，那么这种方法显然是无效的。
我们如何减少内存消耗？下面是使用O（n）额外空间的详细算法，其中n是输入数组中的元素数。 1. 取一个大小为n的辅助数组（比如前缀[]）。 2. 用前缀sum填充它，这样前缀[i]表示从0到i的数字之和。 3. 生成一个介于1和Sum（包括两者）之间的随机数（比如r），其中Sum表示输入频率数组的总和。 4. 在前缀数组中查找步骤#3中生成的随机数的Ceil索引。让索引成为索引 C . 5. 返回随机数arr[indexc]，其中arr[]包含输入的n个数字。 在我们进入实现部分之前，让我们通过一个例子快速了解一下算法： arr[]：{10,20,30} 频率[]：{2,3,1} 前缀[]：{2,5,6} 因为前缀中的最后一个条目是6，所以r的所有可能值都是[1,2,3,4,5,6] 1:Ceil是2。生成的随机数是10。 2:Ceil是2。生成的随机数是10。 3:Ceil是5。生成的随机数是20。 4:Ceil是5。生成的随机数是20。 5:Ceil是5。生成的随机数是20。 6.Ceil是6。生成的随机数是30。 在上面的例子中 10的概率为2/6。 20以3/6的概率生成。 30的概率为1/6。
这是怎么回事？ 任何数字输入[i]的生成次数与其出现频率相同，因为范围内存在整数计数（前缀[i–1]，前缀[i]]是输入[i]。与上面的示例一样，3是三次生成的，因为有三个整数3、4和5的ceil是5。
C++
// C++ program to generate random numbers // according to given frequency distribution #include <bits/stdc++.h> using namespace std; // Utility function to find ceiling of r in arr[l..h] int findCeil( int arr[], int r, int l, int h) { int mid; while (l < h) { mid = l + ((h - l) >> 1); // Same as mid = (l+h)/2 (r > arr[mid]) ? (l = mid + 1) : (h = mid); } return (arr[l] >= r) ? l : -1; } // The main function that returns a random number // from arr[] according to distribution array // defined by freq[]. n is size of arrays. int myRand( int arr[], int freq[], int n) { // Create and fill prefix array int prefix[n], i; prefix[0] = freq[0]; for (i = 1; i < n; ++i) prefix[i] = prefix[i - 1] + freq[i]; // prefix[n-1] is sum of all frequencies. // Generate a random number with // value from 1 to this sum int r = ( rand () % prefix[n - 1]) + 1; // Find index of ceiling of r in prefix array int indexc = findCeil(prefix, r, 0, n - 1); return arr[indexc]; } // Driver code int main() { int arr[] = {1, 2, 3, 4}; int freq[] = {10, 5, 20, 100}; int i, n = sizeof (arr) / sizeof (arr[0]); // Use a different seed value for every run. srand ( time (NULL)); // Let us generate 10 random numbers according to // given distribution for (i = 0; i < 5; i++) cout << myRand(arr, freq, n) << endl; return 0; } // This is code is contributed by rathbhupendra |
C
//C program to generate random numbers according to given frequency distribution #include <stdio.h> #include <stdlib.h> // Utility function to find ceiling of r in arr[l..h] int findCeil( int arr[], int r, int l, int h) { int mid; while (l < h) { mid = l + ((h - l) >> 1); // Same as mid = (l+h)/2 (r > arr[mid]) ? (l = mid + 1) : (h = mid); } return (arr[l] >= r) ? l : -1; } // The main function that returns a random number from arr[] according to // distribution array defined by freq[]. n is size of arrays. int myRand( int arr[], int freq[], int n) { // Create and fill prefix array int prefix[n], i; prefix[0] = freq[0]; for (i = 1; i < n; ++i) prefix[i] = prefix[i - 1] + freq[i]; // prefix[n-1] is sum of all frequencies. Generate a random number // with value from 1 to this sum int r = ( rand () % prefix[n - 1]) + 1; // Find index of ceiling of r in prefix array int indexc = findCeil(prefix, r, 0, n - 1); return arr[indexc]; } // Driver program to test above functions int main() { int arr[] = {1, 2, 3, 4}; int freq[] = {10, 5, 20, 100}; int i, n = sizeof (arr) / sizeof (arr[0]); // Use a different seed value for every run. srand ( time (NULL)); // Let us generate 10 random numbers according to // given distribution for (i = 0; i < 5; i++) printf ( "%d" , myRand(arr, freq, n)); return 0; } |
JAVA
// Java program to generate random numbers // according to given frequency distribution class GFG { // Utility function to find ceiling of r in arr[l..h] static int findCeil( int arr[], int r, int l, int h) { int mid; while (l < h) { mid = l + ((h - l) >> 1 ); // Same as mid = (l+h)/2 if (r > arr[mid]) l = mid + 1 ; else h = mid; } return (arr[l] >= r) ? l : - 1 ; } // The main function that returns a random number // from arr[] according to distribution array // defined by freq[]. n is size of arrays. static int myRand( int arr[], int freq[], int n) { // Create and fill prefix array int prefix[] = new int [n], i; prefix[ 0 ] = freq[ 0 ]; for (i = 1 ; i < n; ++i) prefix[i] = prefix[i - 1 ] + freq[i]; // prefix[n-1] is sum of all frequencies. // Generate a random number with // value from 1 to this sum int r = (( int )(Math.random()*( 323567 )) % prefix[n - 1 ]) + 1 ; // Find index of ceiling of r in prefix array int indexc = findCeil(prefix, r, 0 , n - 1 ); return arr[indexc]; } // Driver code public static void main(String args[]) { int arr[] = { 1 , 2 , 3 , 4 }; int freq[] = { 10 , 5 , 20 , 100 }; int i, n = arr.length; // Let us generate 10 random numbers according to // given distribution for (i = 0 ; i < 5 ; i++) System.out.println( myRand(arr, freq, n) ); } } // This code is contributed by Arnab Kundu |
Python3
# Python3 program to generate random numbers # according to given frequency distribution import random # Utility function to find ceiling of r in arr[l..h] def findCeil(arr, r, l, h) : while (l < h) : mid = l + ((h - l) >> 1 ); # Same as mid = (l+h)/2 if r > arr[mid] : l = mid + 1 else : h = mid if arr[l] > = r : return l else : return - 1 # The main function that returns a random number # from arr[] according to distribution array # defined by freq[]. n is size of arrays. def myRand(arr, freq, n) : # Create and fill prefix array prefix = [ 0 ] * n prefix[ 0 ] = freq[ 0 ] for i in range (n) : prefix[i] = prefix[i - 1 ] + freq[i] # prefix[n-1] is sum of all frequencies. # Generate a random number with # value from 1 to this sum r = random.randint( 0 , prefix[n - 1 ]) + 1 # Find index of ceiling of r in prefix array indexc = findCeil(prefix, r, 0 , n - 1 ) return arr[indexc] # Driver code arr = [ 1 , 2 , 3 , 4 ] freq = [ 10 , 5 , 20 , 100 ] n = len (arr) # Let us generate 10 random numbers according to # given distribution for i in range ( 5 ) : print (myRand(arr, freq, n)) # This code is contributed by divyesh072019 |
C#
// C# program to generate random numbers // according to given frequency distribution using System; class GFG{ // Utility function to find ceiling // of r in arr[l..h] static int findCeil( int [] arr, int r, int l, int h) { int mid; while (l < h) { // Same as mid = (l+h)/2 mid = l + ((h - l) >> 1); if (r > arr[mid]) l = mid + 1; else h = mid; } return (arr[l] >= r) ? l : -1; } // The main function that returns a random number // from arr[] according to distribution array // defined by freq[]. n is size of arrays. static int myRand( int [] arr, int [] freq, int n) { // Create and fill prefix array int [] prefix = new int [n]; int i; prefix[0] = freq[0]; for (i = 1; i < n; ++i) prefix[i] = prefix[i - 1] + freq[i]; // prefix[n-1] is sum of all frequencies. // Generate a random number with // value from 1 to this sum Random rand = new Random(); int r = (( int )(rand.Next() * (323567)) % prefix[n - 1]) + 1; // Find index of ceiling of r in prefix array int indexc = findCeil(prefix, r, 0, n - 1); return arr[indexc]; } // Driver Code static void Main() { int [] arr = { 1, 2, 3, 4 }; int [] freq = { 10, 5, 20, 100 }; int i, n = arr.Length; // Let us generate 10 random numbers // according to given distribution for (i = 0; i < 5; i++) Console.WriteLine(myRand(arr, freq, n)); } } // This code is contributed by divyeshrabadiya07 |
Javascript
<script> // JavaScript program to generate random numbers // according to given frequency distribution // Utility function to find ceiling of r in arr[l..h] function findCeil(arr, r, l, h) { let mid; while (l < h) { mid = l + ((h - l) >> 1); // Same as mid = (l+h)/2 (r > arr[mid]) ? (l = mid + 1) : (h = mid); } return (arr[l] >= r) ? l : -1; } // The main function that returns a random number // from arr[] according to distribution array // defined by freq[]. n is size of arrays. function myRand(arr, freq, n) { // Create and fill prefix array let prefix= []; let i; prefix[0] = freq[0]; for (i = 1; i < n; ++i) prefix[i] = prefix[i - 1] + freq[i]; // prefix[n-1] is sum of all frequencies. // Generate a random number with // value from 1 to this sum let r = Math.floor((Math.random()* prefix[n - 1])) + 1; // Find index of ceiling of r in prefix array let indexc = findCeil(prefix, r, 0, n - 1); return arr[indexc]; } // Driver code let arr = [1, 2, 3, 4]; let freq = [10, 5, 20, 100]; let i; let n = arr.length; // Use a different seed value for every run. // Let us generate 10 random numbers according to // given distribution for (i = 0; i < 5; i++) document.write(myRand(arr, freq, n)); // This code is contributed by rohitsingh07052. </script> |
输出： 不同的跑步可能会有所不同
43444
时间复杂性： O（n）
本文由 阿希什·巴恩瓦尔 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
