用快速排序完成题目:数组中最小的k个数
来源:5-10 快速排序-基础算法

慕丝5957077
2020-07-08
老师您好,我在leetcode中的写法是这样的,运行超时,但始终不知道问题出在哪里,请问程序里面是哪里有问题
var getLeastNumbers = function(arr, k) {
let len = arr.length
if (!len || !k) return []
let start = 0
let end = len - 1
let index = partition(arr, start, end)
while(index !== k - 1) {
if (index > k-1) {
end = index-1
index = partition(arr, start, end)
} else {
start = index + 1
index = partition(arr, start, end)
}
}
return arr.slice(0, k)
};
function partition(arr, left, right) {
let pivot = arr[Math.floor(left+right)/2]
while(left <=right) {
while(arr[left]<pivot){
left++
}
while(arr[right]>pivot){
right--
}
if(left<=right){
[arr[left],arr[right]]=[arr[right],arr[left]];
left++;
right--;
}
}
return left;
}
写回答
1回答
-
慕粉1926294646
2020-11-07
快排的基本思想:
1)在数据集之中,选择一个元素作为"基准"(pivot)。
2)所有小于"基准"的元素,都移到"基准"的左边;所有大于"基准"的元素,都移到"基准"的右边。
3)对"基准"左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。
可以按这个检测下,在 LeetCode 上查看是哪个输入超时了,打断点调试下,这样自己才能真正的理解
00
相似问题