选择算法

选择问题

从n个元素的集合中选择第i个顺序统计量的问题形式化地归结为“选择问题”。

中位数和顺序统计量

1）顺序统计量：在一个由n个元素组成的集合中，第i个顺序统计量(order statistic)是该集合中的第i小的元素。如：在一个元素集合中，最小值是第1个顺序统计量（i=1）；最大值是第n个顺序统计量（i=n）

2）中位数：对一个有n个元素的集合，将数据排序后，位置在最中间的数称为该集合的中位数。

假设集合中的元素是互异的（可推广至包含重复元素的情形）。

输入：一个包含n个（互异）元素的集合A和一个整数i，1≤i≤n。
输出：元素x∈A，且A中恰好有i-1个其他元素小于它。

解决的办法：

1）排序元素集合排序后，位于第i位的元素即为该集合的第i个顺序统计量。时间复杂度：O(nlogn)

2）选择算法设法找出元素集合里面的第i小元素，该元素为集合的第i个顺序统计量。时间复杂度：O(n)

最大值和最小值问题

在一个有n个元素的集合中，需要做多少次比较才能确定其最小元素或者最大值呢？n-1次，时间：O(n)

这是求解上述问题的最好结果

不失一般性，就变成了求解上述第i小的问题。

快速选择算法（Quick Selection）

通常用来在未排序的数组中寻找第k小/第k大的元素。快速选择及其变种是实际应用中最常使用的高效选择算法。

快速选择的总体思路与快速排序一致，选择一个元素作为基准来对元素进行分区，将小于和大于基准的元素分在基准左边和右边的两个区域。不同的是，快速选择并不递归访问双边，而是只递归进入一边的元素中继续寻找。这降低了平均时间复杂度，从O(nlog n)至**O(n)**，不过最坏情况仍然是O(n^2^)。

Quick Selection原理

Quick Selection算法和Quick Sort算法是由同一个作者提出，这两者之间有很大的相似之处——分治，即将问题的规模一次次的减小，直到求出最终解。

目标：找到第n大的数

随机产生一个pivot
根据这个pivot，将小于其的数放左边，大于其的数放右边
更新第n大数的估计值的位置，选择其中一边，直到=n
重复2、3步骤

Quick Select复杂度分析

1、时间复杂度

完整的平均时间复杂度分析非常复杂，在这里不再赘述。有兴趣的可以看这里。
一般来说，因为我们才用了随机选取pivot的过程，平均来看，我们可以假设每次pivot都能选在中间位置。设算法时间复杂度为T(n)。在第一层循环中，我们将pivot与n个元素进行了比较，这个时间为cn 。
所以第一步时间为：T(n) = cnc + T(n/2)。其中T(n/2)为接下来递归搜索其中一半的子数组所需要的时间。
在递归过程中，我们可以得到如下公式：
T(n/2) = c(n/2) + T(n/4)
T(n/4) = c(n/4) + T(n/8)
…
T(2) = 2c + T(1)
T(1) = 1c
将以上公式循环相加消除T项可以得到：
T(n) = c(n + n/2 + n/4 + n/8 + … + 2 + 1) = 2n = O(n)
因此得到Quick Select算法的时间复杂度为O(n)。

1）造成最坏情况是O(n^2^)的原因分析：类似快速排序的最坏情况。

2、空间复杂度

算法没有使用额外空间，swap操作是inplace操作，所以算法的空间复杂度为O(1)。

Quick Select Java实现

Leetcode 215 Top k

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int begin =0;
        int end = nums.length-1;
        k=nums.length+1-k;
        while(begin<end)
        {
            int pos = quick_select(nums,begin,end);
            if(pos==k-1)break;
            else if(pos<k-1)begin=pos+1;
            else end=pos-1;
        }
        return nums[k-1];
    }
    public int quick_select(int[] s,int right,int left)
    {
        int i=right,j=left;
        int x=s[right];
        while(i<j)
        {
            while(i<j&&s[j]>=x)//找到右边最近一个小于x的值
            j--;
            if(i<j)
            {
                int temp =s[j];
                s[i]=temp;//填坑
                s[j]=s[i];
                i++;
            }//此时 s[j]==x
            //从左向右找数填s[j]
            while(i<j&&s[i]<=x)
            i++;
            if(i<j)
            {
                int temp =s[i];
                s[j]=temp;//填坑
                s[i]=s[j];
                j--;
            }//此时 s[i]==x
        }
        //退出时 i==j，将x填入坑中
        s[i]=x;
        return i;
    }
}

最坏情况为线性时间的选择算法（五分化中项的中项）

本质上还是快速选择算法，但是我们在选择枢纽元的时候，有既定的策略—–五分化中项的中项（也叫中位数的中位数）。这样就可以保证在最坏情况下依然是线行O（n）的复杂度

实现

将输入数组的n个元素划分成[n/5]组，每组5个元素，且最多只有一组由剩下的n mod 5个元素组成
寻找这[n/5]个元素的中位数，首先对这组元素进行插入排序，然后确定每组有序元素的中位数，即第三个元素
把每组找出的中位数重组为一个新的数组，找出其中位数x（递归调用SELECT以找出中位数x，如果由偶数个中位数，约定x是较小的中位数）
使用PARTITION，将x对输入数组进行划分，返回k，低区的k - 1个元素小于x，高区的n - k个元素大于x
（partition的工作原理是将一个数组划分成两段，其中一段的元素都小于主元，另一段数组的元素都大于主元）
比较k和i的大小，如果i < k，在低区递归调用SELECT，如果i > k，在高区递归调用SELECT，如果i = k，直接返回x。

简单来说：我们选择的枢纽元是中位数的中位数X，其他的和快速选择算法一致，递归求解第K大的值。

时间复杂度分析

对于大于中位数的中位数x，大于x的元素个数至少有：
3(⌈1/2⌈n/5⌉⌉−2）⩾3n/10−6
那么，递归至多作用于（7n/10+6）个元素。
算法中的
第(3)步时间复杂度为T(⌈n/5⌉)
第(5)步的时间复杂度为T(7n/10+6)
我们可以得到算法的总时间复杂度为
T(n)≤T(⌈n/5⌉)+T(7n/10+6)+O(n)
假设一个任意常数C，使得T(n)≤cn
又假设O(n)的上界为an
那么带入c，a得到：
T(n)⩽9cn/10+7c+an=cn+(−9n/10+7c+an)
只需要证明: −9n/10+7c+an⩽0 即可
该不等式等价于：c⩾10a(n/(n−70))
所以当n>140时，c⩾20a这样就可以满足不等式。
因此最坏情况下选择算法的运行时间是线性的。

算法描述

//下面给定的是二次取中算法的说明性描述
SELECT2(int a[],int i,int n)
{
    //在集合a中找第i小元素，且n为集合a的元素数量
    if(n<r)
    {
        //采用插入排序直接对a进行分类并返回第i小的元素
    }
    else
    {
        //把a分成大小为r的（n/r）个子集合，忽略多余的元素
    }
    int m[r];//表示这些子集合的中间值集合
    v=SELECT2(m,(n/r)/2,(n/r));//得到中间值的中间值v
        j=PARTITION(a,v);//得到v在a中是第j小元素
    if(i==j)
        return v;
    else if(i<j)//说明要往下区寻找
        return SELECT2(s,i,j-1);//s是a[1：j-1]
    else
        return  SELECT2(R,i-j,n-j);//R是a[j+1:n]
}

算法分析

记T(n)是SELECT2所需的最坏情况时间

对特定的r分析SELECT2：选取r=5。

假定A中的元素各不相同，则有

若n≤r，则采用插入法直接对A分类并返回第i小元素 → Ο(1)
把A分成大小为r的(n/r)个子集合，忽略多余的元素 → Ο(n)
得到m的集合（中间值） → Ο(n)
v=SELECT2(m,(n/r)/2,(n/r));//得到中间值的中间值v → T(n/5)
j=PARTITION(a,v);//得到v在a中是第j小元素 → Ο(n)
else if(i<j)//说明要往下区寻找 → T(3n/4)，当n≥24
return SELECT2(s,i,j-1);//s是a[1：j-1]
else
return SELECT2(R,i-j,n-j);//R是a[j+1:n]

用归纳法(代入法)可证：T(n)≤20cn

故，在r=5地情况下，求解n个不同元素选择问题的算法SELECT2的最坏情况时间是Ο(n)。

进一步分析

若A中有相同的元素时，上述结论T(n)=O(n)可能不成立。

原因：

步骤⑤经PARTITION调用所产生的S和R两个子集合中可能存在一些元素等于划分元素v,可能导致|S|或|R|大于0.7n+1.2，从而影响到算法的效率。

例如：设r=5,且A中有相同元素。不妨假设其中有0.7n+1.2个元素比v小，而其余的元素都等于v。
则，经过PARTITION，这些等于v的元素中至多有一半可能在落在S中，故|S|≤0.7n+1.2+(0.3n-1.2)/2=0.85n+0.6。
同理，|R|≤0.85n+0.6。
可得，此时步骤④和⑥所处理的元素总数将是
T(n/5)+T(0.85n+0.6)≈1.05n+0.6>n
不再是线性关系。故有T(n)≠Ο(n)

改进

方法一：将A集合分成3个子集合U,S和R，其中U是由A中所有与v相同的元素组成，S是由A中所有比v小的元素组成，R则是A中所有比v大的元素组成。

同时步骤⑥更改：

case 
:|S|≥k:return(SELECT2(S,k,|S|)
:|S|+|U|≥k:return(v)
:else: return(SELECT2(R,k-|S|-|U|,|R|))
endcase

从而保证|S|和|R|≤0.7n+1.2成立，故关于T(n)的分析仍然成立。即T(n) = Ο(n)

中位数问题

示例：

石油管的最优位置Olay教授正在为一家石油公司咨询，公司正在计划建造一条由东向西的大型管道。该管道要穿过一个有n口井的油田。从每口井中都有一条喷油管沿最短路径与主管道直接相连(或南或北)

问题：给定各口井的x坐标和y坐标。问，Olay教授如何选择主管道的最优位置，使得喷管长度总和最小？

带权中位数：首先也是将这个数组的数据按一定的顺序排列，带权中位数（Weighted Median）对于n个互不相同的元素集合x1、x2……xn，其权重依次为w1、w2……wn。令W =
$$
\sum_{i=1}^n{Wi}=1
$$
，则带权中位数XK满足：（这里的权重可以用这个数据出现的频率来表示，或者这个数据的重要性）

$$
\sum_{X_i<X_k} W_i<\frac{1}{2}
$$

$$
\sum_{X_i>X_k} W_i<=\frac{1}{2}
$$

带权中位数的应用

（1）一维空间上的问题

一条直线上有若干个带权的点p1,p2,…,pn，它们的权重分别是ω1,ω2,…,ωn，在该直线上寻找一个点p，使得
$$
\sum_{i=1}^nW_id(p,p_i)
$$
最小，其中d(a,b)表示点a与b之间的距离d(a,b)=|a-b|——称点p为该n个点的一维带权中位数。

称点p为该n个点的一维带权中位数。

（2）二维空间上的问题

设二维平面上分布着n个点p1, p2,… pn，点pi的坐标用(xi,yi)表示，每个点附有一个权重ωi，
$$
\sum_{i=1}^n{Wi}=1
$$
。
定义点p1(x1,y1)与点p2(x2,y2)之间的距离是
d(p1, p2)=|x1-x2|+|y1-y2|（称为Manhattan距离）
问题：在二维平面上找一个点p(x,y)，使得
$$
\sum_{i=1}^nW_id(p,p_i)
$$
最小，则称p为该二维平面上n个点的带权中位数。

问题：为什么使
$$
\sum_{i=1}^nW_id(p,p_i)
$$
最小的点满足
$$
\sum_{p_i<p} W_i<=\frac{1}{2}和 \sum_{p_i>p} W_i<\frac{1}{2}？
$$

带权中位数问题常见算法：

1：朴素算法：

方法：枚举集合点，进行计算

时间复杂度：O（N^2）

2：递推算法：

1．朴素递推：

方法：分别计算对于一个点从左右过来的总代价，求其最小值

时间复杂度：O（N）

2．递推改进算法

方法：利用前面证明的结论和带权中位数的定义，只需要一次扫描即可

时间复杂度：O（N）

3：分治算法：

1． O（NlogN）的算法

方法：二分集合点，比较集合点为M与M+1时的谁更优，不断缩小范围

2． O（N）的二分改进算法

方法：二分集合点，但利用了已知信息，将时间复杂度降到O（N）