JS的lintcode学习笔记（5）—— 第k大元素

104 阅读 0 评论 69 点赞

我是靠谱客的博主眼睛大小鸽子，这篇文章主要介绍JS的lintcode学习笔记（5）—— 第k大元素，现在分享给大家，希望可以做个参考。

问题描述：在乱序数组中找到第 k 大的元素。

问题说明：可以交换数组中的元素，时间复杂度为O(n)，空间复杂度为O(1)。

问题分析：首先，我们可以确定，要想找到第k大的数，最简便的方法就是使用冒泡排序，每一轮冒泡得到的就是该轮最大的数，这样循环k轮就可以找到第k大的数。但这种方法时间复杂度过高，数组遍历次数太多，所以不推荐，这里也不用代码实现了。

虽然冒泡时间复杂度过高，但排序的思想是对的，我们可以选择时间复杂度更低的快速排序。这道题本质上只要找到第k大的数即可，我们并不需要将整个数组完整的进行排序。关于快排，可以自行去了解，这里就不详细说明了：http://bubkoo.com/2014/01/12/sort-algorithm/quick-sort/

大致上思路是这样的：我们在数组中任意选择一个数作为基准点（一般第一次默认是数组的第一个数），使用快排的方法，每一轮排完，基准点左边的数都比基准点大，右边的数都比基准点小，这样就有三种情况：

（1）基准点当前的下标等于k-1，则基准点即所求，返回这个数。

（2）基准点当前的下标大于k-1，则所求的数在基准点的左半边，把左半边的前后下标返回给函数进行递归

（3）基准点当前的下标小于k-1，则所求的数在基准点的右半边，把右半边的前后下标返回给函数进行递归

另外。关于JS中交换一个数组中的元素，这里使用的是 arr.splice() 方法，比如若要将下标为 a 和 b 的数进行交换：

复制代码

1
arr[a] = arr.splice(b, 1, arr[a])[0];

关于splice()后的 [0] ,是因为splice的返回值是数组类型，加上[0]是取数组中的元素。

代码实现：ps：不知道为什么在lintcode上通过不了，但用sublime却可以，应该可以用。如有问题，欢迎指出~

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
const kthLargestElement = function (n, nums, start, end) {
    var low = start;
    var high = end;
    var temp = nums[low];       //枢轴点
    
    while(low < high){
        while(low<high && nums[high]<=temp){
            high--;
        }
        //在高位遇到比temp大的值交换到低位
        nums[low] = nums.splice(high, 1, nums[low])[0];
        while(low<high && nums[low]>=temp){
            low++;
        }
        //在低位遇到比temp小的值交换到高位
        nums[high] = nums.splice(low, 1, nums[high])[0];
    }
    //枢轴点回到原位
    nums[high] = temp;
    
    if(high == n-1){
        return  temp;       //当前枢轴点即所求
    }else if(high > n-1){
        return  kthLargestElement(n, nums, start, high-1);
    }else{
        return  kthLargestElement(n, nums, high+1, end);
    }
}