文章目录

前言分治算法之第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;}}