关闭

【LeetCode】常用算法之Quick Select

标签: leetcode算法
3231人阅读 评论(0) 收藏 举报
分类:

之前刚刚实现了快速排序算法。现在还有一个要求就是找到一个序列中第K大的数。

我们当然可以用先排序再取值的方法来做,这样的时间复杂度为O(NlogN)。或者使用heap_sort,或者优先队列,则复杂度是O(NlogK)。

那么有没有一种更加高效的方式呢?答案是肯定的。可以使用快速排序的一个变种quick_select,则平均复杂度为O(N),最坏复杂度为O(N^2)。

算法思想

通过一趟快排过后,序列将被分为(比key小的数,key,比key大的数)三部分,对这一点有疑问的同学可以参考/morewindows/article/details/6684558

那么假设key的下标为i,如果k < i,则第K大的数必然在快排左边的区域;如果k = i,则key就是第k大的数;如果k > i,则k必然在快排的右边的区域。

接下来递归即可得到第k大的数。

算法实现

在快排的基础上修改一下即可。代码没有做输入有效性验证,需要的时候请自行添加。

package tech.mrbcy.algorithm.quickselect;

import java.util.Scanner;

public class QuickSelect {

    // 获得第K大的数
    public int getTopK(int[] nums, int k){
        // 这里稍微注意一下k-1,由于数组下标从0开始,第k大的数下标应该是k-1,所以修改了一下
        return helper(nums, k - 1, 0, nums.length - 1);
    }

    private int helper(int[] nums, int k, int left, int right){
        if(left == right){
            // 只有1个数,那么就是这个数了
            return nums[left];
        }

        int i = left;   // 左边标志位
        int j = right;  // 右边标志位
        int key = nums[i]; // key值

        while(i < j){ 
            // j向前搜索,找到第一个小于key的值
            while(nums[j] >= key && i < j){
                j--;
            }
            // 交换nums[i]和nums[j]
            if(nums[j] < key && i < j){
                nums[i] = nums[j];
                i++; // 填坑后移
            }

            // i向后搜索,找到第一个大于key的值
            while(nums[i] <= key && i < j){
                i++;
            }
            // 交换nums[i]和nums[j]
            if(nums[i] > key && i < j){
                nums[j] = nums[i];
                j--;
            }
        }
        // 现在i 和 j相同,把key填进来
        nums[i] = key;
        // 递归左边部分和右边部分
        if(left < i && k < i){
            return helper(nums, k, left, i - 1);
        }
        if(right > j && k > j){
            return helper(nums, k, j + 1, right);
        }
        return nums[i]; // i == k
    }


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String line = scanner.nextLine();
        String[] strs = line.split(",");
        int[] nums = new int[strs.length];

        int len = strs.length;
        for(int i = 0; i < len; i++){
            nums[i] = Integer.parseInt(strs[i]);
        }

        QuickSelect qs = new QuickSelect();
        int num = qs.getTopK(nums,3);

        // 输出结果
        System.out.println(num);
    }

}

参考资料

/hustyangju/article/details/25399937

0
0
查看评论
发表评论
* 以上用户言论只代表其个人钱柜娱乐开户,不代表CSDN网站的钱柜娱乐开户或立场

快速选择(quick_select) 算法分析

快速选择算法,就是从给定的一个集合S={a1,a2,...an}中选出第K个大小的数,或者给出其所在的下标之类的。 如果使用排序,比如merge_sort,然后返回第K个元素的下标,复杂度是O(Nl...
  • hustyangju
  • hustyangju
  • 2014-05-09 15:48
  • 5247

快速选择(QuickSelect)的平均时间复杂度分析

快选,每次选一部分,扔掉另一部分,所以是O(N) 假设每次扔掉一半. (2^k=N) T(N) =n +n/2+n/4+n/8+n/2^k = n*(1-2^-k)/(1-2^-1) =2N  ...
  • u014421167
  • u014421167
  • 2014-11-13 20:45
  • 1928

quickselect

function partition(list, left, right, pivotIndex) pivotValue := list[pivotIndex] swap ...
  • smallnest
  • smallnest
  • 2011-06-02 14:45
  • 2890

Quick Select Algorithm 快速选择算法

什么是Quick select? Quick select算法通常用来在未排序的数组中寻找第k小/第k大的元素。其方法类似于Quick sort。Quick select和Quick sort都是由T...
  • Yaokai_AssultMaster
  • Yaokai_AssultMaster
  • 2017-03-31 04:38
  • 2450

快速选择(quick select) + 线性时间选择(linear-time select) - 求出n个数中第k大的数

利用快速排序中partition函数,很容易求出n个数中第k大的数,因此在划分后如下图。 左半(包括q)有j = q - p + 1个元素。如果k j,需要在右半找第k - j大元素。可以证明,...
  • jiyanfeng1
  • jiyanfeng1
  • 2013-01-26 06:48
  • 7513

Leetcode常用五大算法思想

分治算法 一、基本概念    在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子...
  • cq361106306
  • cq361106306
  • 2015-04-20 20:57
  • 5639

快速选择(quick_select) 算法分析

快速选择算法,就是从给定的一个集合S={a1,a2,...an}中选出第K个大小的数,或者给出其所在的下标之类的。 如果使用排序,比如merge_sort,然后返回第K个元素的下标,复杂度是O(Nl...
  • hustyangju
  • hustyangju
  • 2014-05-09 15:48
  • 5247

Leetcode:在线编程网站-各大IT公司的笔试面试题

leetcode 是一个美国的在线编程网站,上面主要收集了各大IT公司的笔试面试题,对于应届毕业生找工作是一个不可多得的好帮手。 这个网站的的好处在于它会告诉你测试数据以及你的输出和正确的输出是什么...
  • huixingshao
  • huixingshao
  • 2015-02-09 13:40
  • 13855

排序算法(insert ,shell ,quick ,select , merge ,heap)

排序算法
  • GuitarNian
  • GuitarNian
  • 2016-08-29 18:07
  • 212

快速选择(quick_select) 算法分析

快速选择算法,就是从给定的一个集合S={a1,a2,...an}中选出第K个大小的数,或者给出其所在的下标之类的。 如果使用排序,比如merge_sort,然后返回第K个元素的下标,复杂度是O(Nl...
  • hustyangju
  • hustyangju
  • 2014-05-09 15:48
  • 5247
    个人资料
    • 访问:124777次
    • 积分:2874
    • 等级:
    • 排名:第14277名
    • 原创:187篇
    • 转载:1篇
    • 译文:0篇
    • 评论:6条
    钱柜娱乐开户
    友情链接