用快速排序完成题目:数组中最小的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 上查看是哪个输入超时了,打断点调试下,这样自己才能真正的理解

0
0

JavaScript版 数据结构与算法

填补前端同学的算法短板,掌握面试中最常见的算法与数据结构

2467 学习 · 395 问题

查看课程