一道寻找第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