今天给大家分享一道来自字节跳动的算法面试作为开场！
“给定一个无序数组[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
大家可以思考下如果换成这种问法，那么除了排序法外，是否还有更好的解法？
网友评论