重庆分公司,新征程启航
为企业提供网站建设、域名注册、服务器等服务
输入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); } } }