数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究蓄水池抽样
蓄水池抽样是一种随机算法。在这个算法中，从包含 n 个不同项目的列表中选择 k 个项目。
我们可以通过创建一个大小为 k 的数组作为蓄水池来解决这个问题。然后从主列表中随机选择一个元素，并将该元素放入蓄水池列表中。当一个项目被选中一次后，它将不会被再次选中。但这种方法并不有效，我们可以通过这种方法增加复杂度。
在蓄水池列表中，从列表中复制前 k 个项目，现在从列表中的第 (k+1) 个数字开始，逐个进行，假设当前选择的项目放在索引 i 处。从 0 到 i 中找到一个随机索引，并将其存储到 j 中，如果 j 在 0 到 k 的范围内，则将 reservoir[j] 与 list[i] 交换。
输入和输出
Input:
The list of integers: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}, The value of k = 6
Output:
K-Selected items in the given array: 8 2 7 9 12 6算法
chooseKItems(array, n, k)
输入：数组、数组中的元素数量、要选择的元素数量。
输出：随机选择 k 个元素。
Begin define output array of size [k] copy k first items from array to output while i < n, do j := randomly choose one value from 0 to i if j < k, then output[j] := array[i] increase i by 1 done display output array End
示例
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
void display(int array[], int n) {
for (int i = 0; i < n; i++)
cout << array[i] << " ";
}
void chooseKItems(int array[], int n, int k) { //it will choose k items from the array
int i;
int output[k];
for (i = 0; i < k; i++)
output[i] = array[i];
srand(time(NULL)); //use time function to get different seed value
while(i < n) {
int j = rand() % (i+1); //random index from 0 to i
if (j < k) //copy ith element to jth element in the output array
output[j] = array[i];
i++;
}
cout << "K-Selected items in the given array: ";
display(output, k);
}
int main() {
int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
int n = 12;
int k = 6;
chooseKItems(array, n, k);
}输出
K-Selected items in the given array: 8 2 7 9 12 6
更新于： 2020年6月17日
948 次查看
广告