无序数组求给定值是第K大的元素-轻识

从今天起我将单独开设「码农题库」专栏，持续为大家分享总结各大厂的技术面试题及解题思路，并将对此进行分类汇总，形成海量免费题库，方便大家升职加薪！希望大家支持！今天先给大家分享一道来自字节跳动的算法面试作为开场！

“给定一个无序数组[2,3,6,5,1,7,8]，求给定的元素是第K大的元素？”

示例：

例如输入：n=7，那么在这个数组中7是第6大的元素，所以K=6

这是一道非常常见的算法面试题，最近有朋友反馈在头条的面试中也遇到了这道题，今天就具体和大家聊聊这道题的解法以及它背后的算法知识。

从解法上看，主要思路如下：

“先将这个无序数组由小到大进行排序，然后在排好序的数组中查找给定元素的下标，而找到数组下标也就知道是第几大的元素了”。

但这也涉及，到底该采用何种排序算法，以及排序后如何查找给定元素的问题！而这将考察到候选人对于常用排序、查找算法知识的掌握情况。

先回顾下常用的排序算法，具体如下表所示：

以上表格总结了常见的排序算法及其算法复杂度情况，其中冒泡排序、鸡尾酒排序(冒泡排序的改进版)、选择排序、插入排序的时间复杂度都是O(n^2)指数级，所以如果采用此类算法来解答此题，即便在写对的情况下，面试官肯定也会继续问你有没有时间复杂度更低的解法。

所以要基本Get到本题考查的点，至少要采用快速排序、归并排序、堆排序或计数排序中的一种来实现数组的排序。而完成排序后如何在有序数组中查找指定元素，则需要根据常用的查找算法选择一种时间复杂度更低的。常用的查找算法有：

方法1：快速排序/二分查找

接下来我们以快速排序/二分查找的方式来解答下此题，代码如下：

public class OneDisorderArraySortAndFind {

    public static void main(String args[]) {
        int n = 5;
        int[] array = new int[]{2, 3, 6, 5, 1, 7, 8};
        //先对无序数组进行排序,得到有序数组
        quickSort(array, 0, array.length - 1);
        //二分查找
        int k = binarySearch(array, n) + 1;
        System.out.println("元素{" + n + "}是第" + k + "大的元素");
    }

    /**
     * 数组排序算法（快速排序）
     */
    public static void quickSort(int[] array, int startIndex, int endIndex) {
        //递归结束条件：startIndex大等于endIndex的时候
        if (startIndex >= endIndex) {
            return;
        }
        //得到基准元素位置
        int pivotIndex = partition(array, startIndex, endIndex);
        //用分治法递归数例的两部分
        quickSort(array, startIndex, pivotIndex - 1);
        quickSort(array, pivotIndex + 1, endIndex);
    }

    /**
     * 快速排序得到基准元素
     */
    private static int partition(int[] array, int startIndex, int endIndex) {
        //取第一个位置的元素作为基准元素
        int pivot = array[startIndex];
        int left = startIndex;
        int right = endIndex;
        //坑的位置，初始值等于pivot的位置
        int index = startIndex;
        //大循环在左右指针重合或者交错的时候结束
        while (right >= left) {
            //right指针从右向左进行比较
            while (right >= left) {
                if (array[right] < pivot) {
                    array[left] = array[right];
                    index = right;
                    left++;
                    break;
                }
                right--;
            }
            //left指针从左向右进行比较
            while (right >= left) {
                if (array[left] > pivot) {
                    array[right] = array[left];
                    index = left;
                    right--;
                    break;
                }
                left++;
            }
        }
        array[index] = pivot;
        return index;
    }

    /**
     * 查找算法-查找有序数组中的元素，返回数组下标（二分查找）
     */
    public static int binarySearch(int[] array, int target) {
        //查找范围起点
        int start = 0;
        //查找范围终点
        int end = array.length - 1;
        //查找范围中位数
        int mid;
        while (start <= end) {
            //mid=(start+end)/2 有可能溢出
            mid = start + (end - start) / 2;
            if (array[mid] == target) {
                return mid;
            } else if (array[mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return -1;
    }
}

方法2：堆排序/二分查找

快速排序算法在时间复杂度上并不固定，其平均时间复杂度是O(nlogn)，但其最坏的情况下时间复杂度可能得到O(n^2)。所以我们还可以利用基于二叉堆的堆排序算法来解这道题，具体代码如下：

public class OneDisorderArraySortAndFind {

    public static void main(String args[]) {
        int n = 1;
        int[] array = new int[]{2, 3, 6, 5, 1, 7, 8};
        //堆排序
        heapSort(array);
        //二分查找
        int k = binarySearch(array, n) + 1;
        System.out.println("元素{" + n + "}是第" + k + "大的元素");
    }

    /**
     * 数组排序算法（堆排序）
     *
     * @param array
     */
    public static void heapSort(int[] array) {
        //1.把无序数组构建成二叉堆
        for (int i = (array.length - 2) / 2; i >= 0; i--) {
            downAdjust(array, i, array.length);
        }
        System.out.println(Arrays.toString(array));
        //2.循环删除堆顶元，移到集合尾部，调节堆产生新的堆顶
        for (int i = array.length - 1; i > 0; i--) {
            //最后一个元素和第一元素进行交换
            int temp = array[i];
            array[i] = array[0];
            array[0] = temp;
            //下沉调整最大堆
            downAdjust(array, 0, i);
        }
    }

    /**
     * 下沉调整
     *
     * @param array       待调整的堆
     * @param parentIndex 要下沉的父节点
     * @param length      堆的有效大小
     */
    private static void downAdjust(int[] array, int parentIndex, int length) {
        //temp保存父节点
        int temp = array[parentIndex];
        int childIndex = 2 * parentIndex + 1;
        while (childIndex < length) {
            //如果有右孩子，且右孩子大于左孩子的值，则定位到右孩子
            if (childIndex + 1 < length && array[childIndex + 1] > array[childIndex]) {
                childIndex++;
            }
            //如果父节点小于任何一个孩子的值，直接跳出
            if (temp >= array[childIndex]) {
                break;
            }
            //无需真正交换，单向赋值即可
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = 2 * childIndex + 1;
        }
        array[parentIndex] = temp;
    }

    /**
     * 查找算法-查找有序数组中的元素，返回数组下标（二分查找）
     *
     * @param array
     * @param target
     * @return
     */
    public static int binarySearch(int[] array, int target) {
        //查找范围起点
        int start = 0;
        //查找范围终点
        int end = array.length - 1;
        //查找范围中位数
        int mid;
        while (start <= end) {
            //mid=(start+end)/2 有可能溢出
            mid = start + (end - start) / 2;
            if (array[mid] == target) {
                return mid;
            } else if (array[mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return -1;
    } 
}

上面提到的排序算法及二分查找法是计算机领域的基础算法，也是面试中经常考察到的点，所以要顺利通过面试，还需要多花时间真正掌握。但对于本题来说，排序会无端对不需要的查找的元素进行处理，所以在一定程度上增加了算法的消耗，其时间复杂度为O(nlogn)。

需要注意本题还会经常考到另外一种类型，具体如下：

"给定一个无序数组[2,3,6,5,1,7,8]，求第K大的元素？"

示例：

例如输入：k=1，那么在这个数组中8是第1大的元素，所以K=1的结果是8

大家可以思考下如果换成这种问法，那么除了排序法外，是否还有更好的解法？

—————END—————

来源:字节跳动 | 分类:算法 | 难度:中等 | 频率:高