从今天起我将单独开设「码农题库」专栏，持续为大家分享总结各大厂的技术面试题及解题思路，并将对此进行分类汇总，形成海量免费题库，方便大家升职加薪！希望大家支持！今天先给大家分享一道来自字节跳动的算法面试作为开场！
“给定一个无序数组[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—————
来源:字节跳动 | 分类:算法 | 难度:中等 | 频率:高
