無序數(shù)組求給定值是第K大的元素
從今天起我將單獨開設(shè)「碼農(nóng)題庫」專欄，持續(xù)為大家分享總結(jié)各大廠的技術(shù)面試題及解題思路，并將對此進行分類匯總，形成海量免費題庫，方便大家升職加薪！希望大家支持！今天先給大家分享一道來自字節(jié)跳動的算法面試作為開場！
“給定一個無序數(shù)組[2,3,6,5,1,7,8]，求給定的元素是第K大的元素？”
示例：
例如輸入：n=7，那么在這個數(shù)組中7是第6大的元素，所以K=6
這是一道非常常見的算法面試題，最近有朋友反饋在頭條的面試中也遇到了這道題，今天就具體和大家聊聊這道題的解法以及它背后的算法知識。
從解法上看，主要思路如下：
但這也涉及，到底該采用何種排序算法，以及排序后如何查找給定元素的問題！而這將考察到候選人對于常用排序、查找算法知識的掌握情況。
先回顧下常用的排序算法，具體如下表所示：
以上表格總結(jié)了常見的排序算法及其算法復(fù)雜度情況，其中冒泡排序、雞尾酒排序(冒泡排序的改進版)、選擇排序、插入排序的時間復(fù)雜度都是O(n^2)指數(shù)級，所以如果采用此類算法來解答此題，即便在寫對的情況下，面試官肯定也會繼續(xù)問你有沒有時間復(fù)雜度更低的解法。
所以要基本Get到本題考查的點，至少要采用快速排序、歸并排序、堆排序或計數(shù)排序中的一種來實現(xiàn)數(shù)組的排序。而完成排序后如何在有序數(shù)組中查找指定元素，則需要根據(jù)常用的查找算法選擇一種時間復(fù)雜度更低的。常用的查找算法有：
方法1：快速排序/二分查找
接下來我們以快速排序/二分查找的方式來解答下此題，代碼如下：
public?class?OneDisorderArraySortAndFind?{
????public?static?void?main(String?args[])?{
????????int?n?=?5;
????????int[]?array?=?new?int[]{2,?3,?6,?5,?1,?7,?8};
????????//先對無序數(shù)組進行排序,得到有序數(shù)組
????????quickSort(array,?0,?array.length?-?1);
????????//二分查找
????????int?k?=?binarySearch(array,?n)?+?1;
????????System.out.println("元素{"?+?n?+?"}是第"?+?k?+?"大的元素");
????}
????/**
?????*?數(shù)組排序算法（快速排序）
?????*/
????public?static?void?quickSort(int[]?array,?int?startIndex,?int?endIndex)?{
????????//遞歸結(jié)束條件：startIndex大等于endIndex的時候
????????if?(startIndex?>=?endIndex)?{
????????????return;
????????}
????????//得到基準(zhǔn)元素位置
????????int?pivotIndex?=?partition(array,?startIndex,?endIndex);
????????//用分治法遞歸數(shù)例的兩部分
????????quickSort(array,?startIndex,?pivotIndex?-?1);
????????quickSort(array,?pivotIndex?+?1,?endIndex);
????}
????/**
?????*?快速排序得到基準(zhǔn)元素
?????*/
????private?static?int?partition(int[]?array,?int?startIndex,?int?endIndex)?{
????????//取第一個位置的元素作為基準(zhǔn)元素
????????int?pivot?=?array[startIndex];
????????int?left?=?startIndex;
????????int?right?=?endIndex;
????????//坑的位置，初始值等于pivot的位置
????????int?index?=?startIndex;
????????//大循環(huán)在左右指針重合或者交錯的時候結(jié)束
????????while?(right?>=?left)?{
????????????//right指針從右向左進行比較
????????????while?(right?>=?left)?{
????????????????if?(array[right]?????????????????????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;
????}
????/**
?????*?查找算法-查找有序數(shù)組中的元素，返回數(shù)組下標(biāo)（二分查找）
?????*/
????public?static?int?binarySearch(int[]?array,?int?target)?{
????????//查找范圍起點
????????int?start?=?0;
????????//查找范圍終點
????????int?end?=?array.length?-?1;
????????//查找范圍中位數(shù)
????????int?mid;
????????while?(start?<=?end)?{
????????????//mid=(start+end)/2?有可能溢出
????????????mid?=?start?+?(end?-?start)?/?2;
????????????if?(array[mid]?==?target)?{
????????????????return?mid;
????????????}?else?if?(array[mid]?????????????????start?=?mid?+?1;
????????????}?else?{
????????????????end?=?mid?-?1;
????????????}
????????}
????????return?-1;
????}
}方法2：堆排序/二分查找
快速排序算法在時間復(fù)雜度上并不固定，其平均時間復(fù)雜度是O(nlogn)，但其最壞的情況下時間復(fù)雜度可能得到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?+?"大的元素");
????}
????/**
?????*?數(shù)組排序算法（堆排序）
?????*
?????*?@param?array
?????*/
????public?static?void?heapSort(int[]?array)?{
????????//1.把無序數(shù)組構(gòu)建成二叉堆
????????for?(int?i?=?(array.length?-?2)?/?2;?i?>=?0;?i--)?{
????????????downAdjust(array,?i,?array.length);
????????}
????????System.out.println(Arrays.toString(array));
????????//2.循環(huán)刪除堆頂元，移到集合尾部，調(diào)節(jié)堆產(chǎn)生新的堆頂
????????for?(int?i?=?array.length?-?1;?i?>?0;?i--)?{
????????????//最后一個元素和第一元素進行交換
????????????int?temp?=?array[i];
????????????array[i]?=?array[0];
????????????array[0]?=?temp;
????????????//下沉調(diào)整最大堆
????????????downAdjust(array,?0,?i);
????????}
????}
????/**
?????*?下沉調(diào)整
?????*
?????*?@param?array???????待調(diào)整的堆
?????*?@param?parentIndex?要下沉的父節(jié)點
?????*?@param?length??????堆的有效大小
?????*/
????private?static?void?downAdjust(int[]?array,?int?parentIndex,?int?length)?{
????????//temp保存父節(jié)點
????????int?temp?=?array[parentIndex];
????????int?childIndex?=?2?*?parentIndex?+?1;
????????while?(childIndex?????????????//如果有右孩子，且右孩子大于左孩子的值，則定位到右孩子
????????????if?(childIndex?+?1?1]?>?array[childIndex])?{
????????????????childIndex++;
????????????}
????????????//如果父節(jié)點小于任何一個孩子的值，直接跳出
????????????if?(temp?>=?array[childIndex])?{
????????????????break;
????????????}
????????????//無需真正交換，單向賦值即可
????????????array[parentIndex]?=?array[childIndex];
????????????parentIndex?=?childIndex;
????????????childIndex?=?2?*?childIndex?+?1;
????????}
????????array[parentIndex]?=?temp;
????}
????/**
?????*?查找算法-查找有序數(shù)組中的元素，返回數(shù)組下標(biāo)（二分查找）
?????*
?????*?@param?array
?????*?@param?target
?????*?@return
?????*/
????public?static?int?binarySearch(int[]?array,?int?target)?{
????????//查找范圍起點
????????int?start?=?0;
????????//查找范圍終點
????????int?end?=?array.length?-?1;
????????//查找范圍中位數(shù)
????????int?mid;
????????while?(start?<=?end)?{
????????????//mid=(start+end)/2?有可能溢出
????????????mid?=?start?+?(end?-?start)?/?2;
????????????if?(array[mid]?==?target)?{
????????????????return?mid;
????????????}?else?if?(array[mid]?????????????????start?=?mid?+?1;
????????????}?else?{
????????????????end?=?mid?-?1;
????????????}
????????}
????????return?-1;
????}?
}
上面提到的排序算法及二分查找法是計算機領(lǐng)域的基礎(chǔ)算法，也是面試中經(jīng)?？疾斓降狞c，所以要順利通過面試，還需要多花時間真正掌握。但對于本題來說，排序會無端對不需要的查找的元素進行處理，所以在一定程度上增加了算法的消耗，其時間復(fù)雜度為O(nlogn)。
需要注意本題還會經(jīng)?？嫉搅硗庖环N類型，具體如下：
"給定一個無序數(shù)組[2,3,6,5,1,7,8]，求第K大的元素？"
示例：
例如輸入：k=1，那么在這個數(shù)組中8是第1大的元素，所以K=1的結(jié)果是8
大家可以思考下如果換成這種問法，那么除了排序法外，是否還有更好的解法？
—————END—————
來源:字節(jié)跳動 | 分類:算法 | 難度:中等 | 頻率:高
評論
圖片
表情