算法 系列博客

【算法】刷題范圍建議 和 代碼規(guī)范
【算法】復雜度理論 ( 時間復雜度 )

【字符串】最長回文子串 ( 蠻力算法 )
【字符串】最長回文子串 ( 中心線枚舉算法 )
【字符串】最長回文子串 ( 動態(tài)規(guī)劃算法 ) ★
【字符串】字符串查找 ( 蠻力算法 )
【字符串】字符串查找 ( Rabin-Karp 算法 )

【算法】雙指針算法 ( 雙指針算法分類 | 相向雙指針 | 有效回文串 )
【算法】雙指針算法 ( 有效回文串 II )
【算法】哈希表 ( 兩數(shù)之和 )

【算法】快速排序
【算法】歸并排序
【算法】快速排序與歸并排序?qū)Ρ?br /> 【算法】快速選擇算法 ( 數(shù)組中找第 K 大元素 )

---

文章目錄

• 算法 系列博客
• 一、快速選擇算法

一、快速選擇算法

---

數(shù)組中找第 K 大元素 : https://www.lintcode.com/problem/5/

可以 先進行 快速排序 , 然后找第 k 大的元素 ;

先排序 , 在獲取值 , 會消耗 排序的時間復雜度 $O(n\log n)$ ;

使用 快速選擇算法 , 可以達到 $O(n)$ 的時間復雜度 ;

快速選擇算法 利用了快速排序算法的步驟 , 快速排序的第一個步驟是從數(shù)組中 挑選一個元素 p , 依據(jù) p 將數(shù)組分為兩部分 , 左側(cè)是小于等于 p 的部分 , 右側(cè)是大于等于 p 的部分 ;
上述步驟的時間復雜度是 $O(n)$ ;

分割后 , 左邊有 m 個數(shù) , 右邊有 n 個數(shù) ;

• 假如 k <= m , 則說明要取的值在左側(cè) , 右側(cè)就不用進行排序了 ;
• 假如 k > m , 則說明要取的值在右側(cè) , 左側(cè)就不用排序了 ;

這樣 , 要處理的數(shù)據(jù)規(guī)模就縮小了一半 ;

時間復雜度分析 : 通過 $O(n)$ 的時間復雜度 , 進行了第一次分割 , 將數(shù)組分為左右兩部分 ;

$T(n)=O(n)+T(\frac{n}{2})$
$=O(n)+T(\frac{n}{2})$
$=O(n)+O(\frac{n}{2})+T(\frac{n}{4})$

時間復雜度計算時 , 只考慮最高次項 , 忽略常數(shù) , 忽略系數(shù) ,

最終的時間復雜度是 $O(n)$ ;

因此使用快速選擇算法 , 找數(shù)組中的第 K 大元素 , 時間復雜度是 $O(n)$ ;

代碼示例 :

class Solution {/*** 快速選擇算法* 第 K 大元素* @param k* @param array* @return*/public int kthLargestElement(int k, int[] array) {if (array == null){return -1;}return quickSelect(array, 0, array.length - 1, k);}// 在 array 數(shù)組中, 從 start 到 end 中找到第 k 大元素private int quickSelect(int[] array, int start, int end, int k) {if (start == end) {// 說明此時找到了第 K 大元素return array[start];}// 左右兩個指針及中間元素值int left = start, right = end, pivot = array[(start + end) / 2];while (left <= right) {while (left <= right && array[left] > pivot) {// 默認自增, 如果遇到一個元素大于中心值, 則退出循環(huán), 記錄該元素索引 leftleft++;}while (left <= right && array[right] < pivot) {// 默認自增, 如果遇到一個元素小于中心值, 則退出循環(huán), 記錄該元素索引 rightright--;}// 交換兩個元素if (left <= right) {int tmp = array[left];array[left] = array[right];array[right] = tmp;// 交換完畢后, 左指針自增, 右指針自減, 繼續(xù)向后執(zhí)行left++;right--;}}// 分割完成, 此時索引的排列 start right left end , 其中 right 和 left 之間可能還有元素// 這里涉及到了 3 部分 , start 到 right 之間, right 到 left 之間, left 到 end 之間// right 到 left 之間只可能有 1 個數(shù)// 判定 k 在哪個部分if (start + k - 1 <= right) {// 左側(cè)部分 : 第 k 個數(shù)在 start 到 right 之間return quickSelect(array, start, right, k);}if (start + k - 1 >= left) {// 右側(cè)部分 : 第 k 個數(shù)在 left 到 end 之間// 左側(cè)有 left - start 個數(shù), 總共 k 個數(shù), 在右邊只需要找第 k - (left - start) 個數(shù)return quickSelect(array, left, end, k - (left - start));}// 如果上述兩種情況都不是, 則是中間部分, right 到 left 之間的一個數(shù), 可以寫成 right + 1 或 left - 1return array[right + 1];} }

總結(jié)

以上是生活随笔為你收集整理的【算法】快速选择算法 ( 数组中找第 K 大元素 )的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。