文章目录
前言分治算法之第k小元素分治算法之第k大元素前言
问题:给定线性序列中 n 个元素和一个整数 k ,1 ≤ k ≤ n,要求找出元素中的第 k 小的元素 或者 第 k 大元素,要求是线性时间算法,即时间复杂度为O( n )。需要用到快速排序的分区思想,有关分治法思想和快速排序文章:【算法】分治算法分治算法之第k小元素
问题:给定线性序列中 n 个元素和一个整数 k ,1 ≤ k ≤ n,要求找出元素中的第 k 小的元素 ,要求是线性时间算法,即时间复杂度为O( n )。设计思想:(1)随机选择序列中第 i 个作为基准元素,统计比基准元素小的元素个数, 如果 个数 比 k 小,说明我们要找的第 k 小元素在基准后半部分,个数比 k 大,说明在前半部分。
(2)对于无序序列a[s…t],在其中查找第k小元素的过程: 若s=t,即其中只有一个元素,返回a[s]若s!=t,表示该序列中有两个或两个以上元素,以基准为中心将其划分为a[s…i]和a[i+1…t],a[s…i]中所有元素均小于等于a[i],a[i+1…t]中所有元素均大于a[i]
j = i-s+1,统计小于等于a[i]的元素个数
j>=k,第k小元素在a[s…i]中,递归在a[s…i]中寻找第k小元素
j < k,第k小元素在a[i+1…t]中,递归在a[i+1…t]中寻找第k-j小元素
public class Demo {public static void main(String[] args) {int[] arr={3,1,5,7,8,2,9};System.out.println(randomizedSelect(arr, 0, arr.length - 1, 4));}public static int randomizedSelect(int[] a,int s,int t,int k){//a[s,t]//s == t ==>说明只有一个元素, 输出if (s == t){return a[s];}//s < t 二个或二个元素以上//找到基准i 的位置int i = randomizedPartition(a,s,t);//小于等于 基准的个数int j = i - s + 1;//k <= j 说明第k小的元素在 前半部分a[s,i] 反之在后半部分a[i+1,t]if (j >= k){return randomizedSelect(a,s,i,k);}else {return randomizedSelect(a,i+1,t,k-j);}}//随机产生一个基准的下标===》与第1个元素交换===》分区public static int randomizedPartition(int[] a,int p,int q){//a[p,q]int r = random(p,q);swap(a,r,p);int i = partition(a, p, q);return i;}/*** 以第一个元素为基准 分区* @param a 数组a* @param p a[p,q]* @param q a[p,q]* @return 分区后基准下标i a[p,i]和a[i+1,q]*/public static int partition(int[] a,int p,int q){int x = a[p];int i = p;for (int j = p; j <= q; j++) {if (a[j] < x){i++;swap(a,i,j);}}swap(a,p,i);return i;}/*** 数组交换函数* @param a 数组a* @param p 下标p* @param q 下标q*/public static void swap(int[] a,int p,int q){int t = a[p];a[p] = a[q];a[q] = t;}/*** 产生一个[p,q]的随机数* @param p [p,q]* @param q [p,q]* @return [p,q]的随机数*/public static int random(int p,int q){Random random = new Random();return Math.abs(random.nextInt())%(q-p+1) + p;}}
时间复杂度分析
一个无序数列随机找到一个下标作为基准,每次分区,数列减少一部分,因为每次可以确定第 k 小元素是在基准的前半部分,还是后半部分,如果确定在前半部分,后半部分的数就不需要管了,
T(n)=T(n/b)+O(n)=O(n)
分治算法之第k大元素
在前面那个算法改成比基准大的元素放在前半部分,小的放在后半部分即可。
public class Demo {public static void main(String[] args) {int[] arr={3,1,5,7,8,2,9};System.out.println(randomizedSelect(arr, 0, arr.length - 1, 1));}public static int randomizedSelect(int[] a,int s,int t,int k){//a[s,t]//s == t ==>说明只有一个元素, 输出if (s == t){return a[s];}//s < t 二个或二个元素以上//找到基准i 的位置int i = randomizedPartition(a,s,t);//大于等于 基准的个数int j = i - s + 1;//k <= j 说明第k大的元素在 前半部分a[s,i] 反之在后半部分a[i+1,t]if (j >= k){return randomizedSelect(a,s,i,k);}else {return randomizedSelect(a,i+1,t,k-j);}}//随机产生一个基准的下标===》与第1个元素交换===》分区public static int randomizedPartition(int[] a,int p,int q){//a[p,q]int r = random(p,q);swap(a,r,p);int i = partition(a, p, q);return i;}/*** 以第一个元素为基准 分区* @param a 数组a* @param p a[p,q]* @param q a[p,q]* @return 分区后基准下标i a[p,i]和a[i+1,q]*/public static int partition(int[] a,int p,int q){int x = a[p];int i = p;for (int j = p; j <= q; j++) {if (a[j] > x){i++;swap(a,i,j);}}swap(a,p,i);return i;}/*** 数组交换函数* @param a 数组a* @param p 下标p* @param q 下标q*/public static void swap(int[] a,int p,int q){int t = a[p];a[p] = a[q];a[q] = t;}/*** 产生一个[p,q]的随机数* @param p [p,q]* @param q [p,q]* @return [p,q]的随机数*/public static int random(int p,int q){Random random = new Random();return Math.abs(random.nextInt())%(q-p+1) + p;}}