|
见《剑指offer》167页。 void GetLeastNumbers(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];
}
时间复杂度为什么是O(n) ? |
|
#11分 |
这个是使用计数排序的吧？不过，用堆来做个人感觉更常见上些
|
#21分 |
假设 Partition(input, n, start, end); 为 index++;
那么 for(int index = 0; index < k; index++) ;的时间复杂度为多少? |
#317分 |
因为每次递归只进入一边，所以复杂度是 O(n).
|
#4 |
回复2楼: 每次 Partition都要扫描一次数组，按照你这种说法时间复杂度就是o(nk)了 |
#51分 |
象是select 算法, 记忆中应该是期望时间是O(n), 有兴趣翻一下 CLRS顺序统计量那章,上面有证明
|
#6 |
回复1楼: |
#7 |
回复5楼: 这是快排中的划分方法。快排必须递归到logn层，而求最小k个数可能只需要划分几次就找到index了。 |
#8 |
回复3楼: 是这个道理。在回复别人的时候突然想通了，快排是必须要向下递归的，而上面这个并不需要递归，而是类似折半。 1+1/2+1/4+1/8+…<2 ，o(2n)=o(n)，所以时间复杂度是o(n)。 |
CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明求无序数组中的最小K个数，划分法时间复杂度是O(n)！
