无序数组求给定值是第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—————
来源:字节跳动 | 分类:算法 | 难度:中等 | 频率:高