欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

一道寻找第K大数字的面试题

程序员文章站 2022-06-19 08:45:30
前言前几天看到一道这样一道面试题,在数组中,寻找第k大的值,我们看到这一道题,我们最先想到的就说直接排序,我们可以采用快速排序,时间复杂度能达到O(nlogn),空间复杂度能达到O(1)。但是我们并不需要把所有的数组排好序,所以我们可以在快速排序的基础上做一点调整。思路实现的原理是这样子的:首先我们找一个基准数,就和快速排序一样,接着把小于基准数的元素移动到数组左边,接着把大于基准数的元素移动到数组右边,这时候,基准数的下标肯定在对应的位置上,也就是第i+1大的数,所以只需要判断当前位置的数与k的大小...

前言

前几天看到一道这样一道面试题,在数组中,寻找第k大的值,我们看到这一道题,我们最先想到的就说直接排序,我们可以采用快速排序,时间复杂度能达到O(nlogn),空间复杂度能达到O(1)。但是我们并不需要把所有的数组排好序,所以我们可以在快速排序的基础上做一点调整。

思路

实现的原理是这样子的:首先我们找一个基准数,就和快速排序一样,接着把小于基准数的元素移动到数组左边,接着把大于基准数的元素移动到数组右边,这时候,基准数的下标肯定在对应的位置上,也就是第i+1大的数,所以只需要判断当前位置的数与k的大小就可以了。如果i+1等于k,说明找到了;如果i+1小于k,则说明我们要找的k正在数组的左部分;如果i+1大于k,则说明我们要找的k正在数组的右部分。
直接上代码!!!

package interview;

/**
 * @author xing xing
 */
public class KNumber {
    public static void main(String[] args) {

		//定义数组
        int [] array = {2,7,100,51,-1,20,21};
        
		//求第k大的值
        findK(array, 0, array.length - 1, 7);


    }

    public static void findK(int [] array,int begin,int end,int k) {
      int i = partition(array,begin,end);
          //由于下标是从0开始,所以我们i+1
          //当第i+1的位置大于k的位置时,我们就去左半部分找
      if (i+1>k) {
          findK(array,begin,i-1,k);
          //当第i+1的位置小于k的位置时,我们就去右半部分找
      }else if (i+1<k) {
          findK(array,i+1,end,k);
      }else {
          //如果i+1等于k说明我们找到了
          System.out.println("第K大值为:"+array[i]);
          return ;
      }

    }
	//找到i的位置
    public static int partition(int [] array,int begin,int end) {
        if(begin < end) {
           int key = array[begin];
            while(begin < end) {
                while (begin < end && key < array[end]){
                    end--;
                }
                if (begin < end) {
                    array[begin] = array[end];
                    begin++;
                }
                while (key > array[begin] && begin < end) {
                    begin++;
                }
                if (begin < end) {
                    array[end] = array[begin];
                    end--;
                }

            }
            array[begin] = key;

        }
        return begin;
    }
}

总结

下面我们分析一下性能,首先空间复杂度为O(1),时间复杂度为O(n),性能非常好,不过这个算法有点绕,需要多多理解。

本文地址:https://blog.csdn.net/qq_42627977/article/details/109965315