文章目录
算法 系列博客
一、快速选择算法
一、快速选择算法
数组中找第 K 大元素 : https://www.lintcode.com/problem/5/
可以 先进行 快速排序 , 然后找第 k 大的元素 ;
先排序 , 在获取值 , 会消耗 排序的时间复杂度 O ( n log n ) O(n \log n)O(nlogn) ;
使用 快速选择算法 , 可以达到 O ( n ) O(n)O(n) 的时间复杂度 ;
快速选择算法 利用了快速排序算法的步骤 , 快速排序的第一个步骤是从数组中 挑选一个元素 p , 依据 p 将数组分为两部分 , 左侧是小于等于 p 的部分 , 右侧是大于等于 p 的部分 ;
上述步骤的时间复杂度是 O ( n ) O(n)O(n) ;
分割后 , 左边有 m 个数 , 右边有 n 个数 ;
假如 k <= m , 则说明要取的值在左侧 , 右侧就不用进行排序了 ;
假如 k > m , 则说明要取的值在右侧 , 左侧就不用排序了 ;
这样 , 要处理的数据规模就缩小了一半 ;
时间复杂度分析 : 通过 O ( n ) O(n)O(n) 的时间复杂度 , 进行了第一次分割 , 将数组分为左右两部分 ;
T ( n ) = O ( n ) + T ( n 2 ) T(n) = O(n) + T(\cfrac{n}{2})T(n)=O(n)+T(
2
n
)
= O ( n ) + T ( n 2 ) \ \ \ \ \ \ \ \ \ = O(n) + T(\cfrac{n}{2}) =O(n)+T(
2
n
)
= O ( n ) + O ( n 2 ) + T ( n 4 ) \ \ \ \ \ \ \ \ \ = O(n) + O(\cfrac{n}{2}) + T(\cfrac{n}{4}) =O(n)+O(
2
n
)+T(
4
n
)
时间复杂度计算时 , 只考虑最高次项 , 忽略常数 , 忽略系数 ,
最终的时间复杂度是 O ( n ) O(n)O(n) ;
因此使用快速选择算法 , 找数组中的第 K 大元素 , 时间复杂度是 O ( n ) O(n)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 数组中, 从 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) { // 默认自增, 如果遇到一个元素大于中心值, 则退出循环, 记录该元素索引 left left++; } while (left <= right && array[right] < pivot) { // 默认自增, 如果遇到一个元素小于中心值, 则退出循环, 记录该元素索引 right right--; } // 交换两个元素 if (left <= right) { int tmp = array[left]; array[left] = array[right]; array[right] = tmp; // 交换完毕后, 左指针自增, 右指针自减, 继续向后执行 left++; right--; } } // 分割完成, 此时索引的排列 start right left end , 其中 right 和 left 之间可能还有元素 // 这里涉及到了 3 部分 , start 到 right 之间, right 到 left 之间, left 到 end 之间 // right 到 left 之间只可能有 1 个数 // 判定 k 在哪个部分 if (start + k - 1 <= right) { // 左侧部分 : 第 k 个数在 start 到 right 之间 return quickSelect(array, start, right, k); } if (start + k - 1 >= left) { // 右侧部分 : 第 k 个数在 left 到 end 之间 // 左侧有 left - start 个数, 总共 k 个数, 在右边只需要找第 k - (left - start) 个数 return quickSelect(array, left, end, k - (left - start)); } // 如果上述两种情况都不是, 则是中间部分, right 到 left 之间的一个数, 可以写成 right + 1 或 left - 1 return array[right + 1]; } }