题目：从M个数中随机的选取N个数。

提示：

• 遍历一次（至少要在O（n））。
• 保证随机（数学上概率相等）。
• 不允许使用随机函数（不是不允许使用，但是注意，不允许在M个数里面利用随机函数随机的取N个数，那就没意义了）。

同样，我把C#/C++代码发在下面。思路在C#代码里面，可以先看思路。这也是我自己和朋友同事讨论的一个方法，不是最好，欢迎讨论。

C# Code#region C# Code

思路#region 思路

//遍历一次，并给每个数字一个随机的权值
//创建一个堆，并通过权值维护这个堆（大根堆）
//从大根堆里取出N个数即随机的取出

#endregion

Code#region Code

namespace Finder
…{
自定义Array#region 自定义Array

//自定义的数据类型，用于堆
public class Array
…{
public int data;
public int randonData;
}

#endregion

Heap#region Heap

public class Heap
…{
private Array[] _array;

public Array[] Init(Array[] array)
…{
_array = array;
GenerateHeap();
return _array;
}

private void GenerateHeap()
…{
for (int i = _array.Length / 2 - 1; i >= 0; i–)
…{
DoMaxHeap(_array, _array.Length, i);
}
}

private void Swap(Array[] array,int i,int big)
…{
Array temp = new Array();
temp = array[i];
array[i] = array[big];
array[big] = temp;
}

private void DoMaxHeap(Array[] array,int heapSize,int i)
…{
int left = i * 2 + 1;
int right = i * 2 + 2;
int big = i;

if (left < heapSize && array[left].randonData > array[big].randonData)
…{
big = left;
}

if (right < heapSize && array[right].randonData > array[big].randonData)
…{
big = right;
}

if (i != big)
…{
Swap(array, i, big);
DoMaxHeap(array, heapSize, big);
}
}
}

#endregion

class Program
…{
待输入的数字#region 待输入的数字
static int[] numbers = …{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
#endregion

static Array[] arrays = new Array[10];

static void Main(string[] args)
…{
Heap heap = new Heap();
//给每个数字一个权值并创建成为自定义的Array类型
GenerateArray();
OutPut(10);
Console.WriteLine(“Find 5 Number“);
//生成并输出5个数字
arrays = heap.Init(arrays);
OutPut(5);
}

static void GenerateArray()
…{
Random random = new Random();

for (int i = 0; i < numbers.Length ; i++)
…{
arrays[i] = new Array();
arrays[i].data = numbers[i];
arrays[i].randonData = random.Next(100);
}
}

static void OutPut(int n)
…{
for (int i = 0; i < arrays.Length && i < n; i++)
…{
Console.WriteLine(string.Format(“{0},{1}“, arrays[i].data, arrays[i].randonData));
}
}
}
}

#endregion

#endregion

C++ Code#region C++ Code

#include <iostream>
#include <time.h>
#define MAX 10

using namespace std;

typedef struct Array
…{
int data;
int randomData;
}Array;

class Heap
…{
public:
Heap();
Array *Init(Array *array);
private:
Array *_array;
void GenerateHeap();
void Swap(Array *array,int i,int big);
void DoMaxHeap(Array *array,int n,int i);
};

Heap::Heap()
…{}

Array *Heap::Init(Array *array)
…{
_array = array;

GenerateHeap();

return _array;
}

void Heap::GenerateHeap()
…{
for(int i=MAX/2-1;i>=0;i–)
…{
DoMaxHeap(_array,MAX,i);
}
}

void Heap::Swap(Array *array,int i,int big)
…{
Array temp;
temp = array[i];
array[i] = array[big];
array[big] = temp;
}

void Heap::DoMaxHeap(Array *array,int heapsize,int i)
…{
int left = 2*i+1;
int right = 2*i+2;

int big = i;

if(left<heapsize&&array[left].randomData>array[big].randomData)
…{
big = left;
}

if(right<heapsize&&array[right].randomData>array[big].randomData)
…{
big = right;
}

if(i!=big)
…{
Swap(array,i,big);
DoMaxHeap(array,heapsize,big);
}
}

void GenerateArray();
void OutPut(int n);

int numbers[MAX] = …{1,2,3,4,5,6,7,8,9,10};
Array *array;

int main()
…{
Heap *heap = new Heap();
GenerateArray();
OutPut(MAX);
heap->Init(array);
cout<<“Find 5 numbers“<<endl;
OutPut(5);
return 0;
}

void GenerateArray()
…{
array = new Array[MAX];
for(int i=0;i<MAX;i++)
…{
array[i].data = numbers[i];
array[i].randomData = rand()%10;
}
}

void OutPut(int n)
…{
if(n>MAX)
…{
cout<<“Error Input“<<endl;
return;
}

for(int i=0;i<MAX&&i<n;i++)
…{
cout<<“{“<<array[i].data<<“,“<<array[i].randomData<<“}“<<endl;
}
}

#endregion