个人博客

秦琦琛

0%

查找第K小问题-分治思想

发表于 更新于 分类于

查找第K小问题-分治

选择问题（select problem）是指在n个元素的集合中，选出某个元素值大小在集合中处于第k位的元素，即所谓的求第k小元素问题(kth-smallest)。

当k=1时，是求最小元素；而当k=n时，就是求最大元素；当k=(n+1)/2时，称为中位数。

一、分治法

假定经过一趟划分后，长度为n的原表被分成左右两个子表，其中，长度为p的左子表包括主元及其左边的元素，右子表包括主元右边的元素。那么：

  • 若k=p，则主元即为第k小元素；
  • 若k<p ，第k小元素必定在左子表中，需求解的子问题成为在左子表中求第k小元素；
  • 若k>p，则第k小元素必定在右子表中，需求解的子问题成为在右子表中求第k-p小元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int SearchK(int A[], int left ,int right , int k){
    if(left > right )
        return -1 ;
    int i = Partition(A,left,right);
    int p = i - left + 1
    if( p == k )
        return A[k];
    if( k < p ){
        return SearchK(A,left,p,k);
    }else{
        return SearchK(A,p+1,right,k-p);
    }
    
}
int Partition(int A[], int left ,int right){
    int priot = A[left] ;
    int i = left , j = right ;
    while(i < j ){
        while( A[j] > priot){
            j-- ;
        }
        A[i] = A[j] ;
        while( A[i] < priot ){
            i++ ;
        }
        A[j] = A[i] ;
    }
    A[i] = priot ;
    return i ;
}

时间复杂度：O(n) 最坏情况下：O(n^2)

二、分治法的进一步加深

image-20211226213017613

对n个元素进行分组，M序列是由每组的中位数组成。中间粉色的就是m*

image-20211226213223263

通过与m*进行比较，将所有元素划分为四个区域。

A、D中的元素分别与m*进行比较，将元素分别划到B、C集合中。

image-20211226213527422

如上图所示，最后将元素分成两个集合，并以m*作为划分点。

image-20211226213722007

1
2
3
int SelectK(int S[], int k){
    
}