输入n个整数，找出其中最小的k个数
解法1：需要修改输入的数组，基于partition快速排序来做，时间复杂福O（N）
分析：基于数组的第k个元素来调整，使的比第k个数大的所有数字放到数组的右边，这样，数组左边k个就是最小的k个数字
void GetLestNumber(int *input, int n, int *output, int k)
{
if (input == NULL || output == NULL || k > n || n <= 0 || k <= 0)
return;
int start = 0;
int end = n - 1;
int index = Partition(input, n, start, end);
while (index != k - 1)
{
if (index > k - 1)
{
end = index - 1;
index = Partition(input, n, start, end);
}
else
{
start = index + 1;
index = Partition(input, n, start, end);
}
}
for (int i = 0; i < k; ++i)
{
output[i] = input[i];
}
}解法二：
分析：先创建一个大小为k的数据容器来存储最小的k个数字，接着每次从输入的n个整数中读入一个数，如果容器中少于k个数则直接放，若大于则表示容器以满，此时找出容器中大值，然后拿输入的值和大值比较，若待插入的数小于大值，则直接替换。
大堆的结构每次可以在O（1）得到大值，但需要o（logk）时间来完成删除及插入
红黑树同上，但是代码简于大堆
void GetLestNumber(int *input, int n, int *output, int k)
{
if (input == NULL || output == NULL || k > n || n <= 0 || k <= 0)
return;
int start = 0;
int end = n - 1;
int index = Partition(input, n, start, end);
while (index != k - 1)
{
if (index > k - 1)
{
end = index - 1;
index = Partition(input, n, start, end);
}
else
{
start = index + 1;
index = Partition(input, n, start, end);
}
}
for (int i = 0; i < k; ++i)
{
output[i] = input[i];
}
}
解法二：
分析：先创建一个大小为k的数据容器来存储最小的k个数字，接着每次从输入的n个整数中读入一个数，如果容器中少于k个数则直接放，若大于则表示容器以满，此时找出容器中大值，然后拿输入的值和大值比较，若待插入的数小于大值，则直接替换。
大堆的结构每次可以在O（1）得到大值，但需要o（logk）时间来完成删除及插入
const int N = 1000;
const int k = 10;
void AdjustDown(int *a, int size, int parent)
{
int child = (parent - 1) / 2;
while (child < size)
{
if (child+1a[child + 1])
child++;
if (a[child]>a[parent])
{
swap(a[child], a[parent]);
parent = child;
child = (parent - 1) / 2;
}
else
break;
}
}
void GetTopK(int*a)
{
assert(k < N);
int top[k];
for (int i = 0; i < k; i++)
{
top[i] = a[i];
}
for (int i = (k - 2) / 2; i >= 0; i++)
{
AdjustDown(top, k, i);
}
for (int i = N-k-1; i < N; i++)
{
if (a[i]>top[0])
{
top[0] = a[i];
AdjustDown(top, k, 0);
}
}
} 创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。
