数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
Microsoft 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日
952 次浏览
广告