第K小数 uva 10041 - Vito's Family poj 2388 Who's in the Middle

     题目链接

      很容易理解题目的意思，就是求某个点到其他点的距离之和，而且要让这个和最小，很明显是求中位数了。

     关于求中位数，一般的方法是我们先将整个数组进行排序，然后直接取出中位数，采用不同的排序方法可能有不同的时间复杂度，一般我们使用快排，时间复杂度为O(nlogn)，有没有更快的方法？ 答案是肯定的。

    这里有一种时间复杂度为O(n)的算法，下面是此题的解题代码。

//uva 10041 - Vito's Family
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;

int a[40000];

int partition(int l, int r)
{
    int x = a[r];
    int i = l-1;
    for (int j = l; j < r; j++)
    {
        if (x >= a[j])
        {
            i++;
            swap(a[i], a[j]);
        }
    }
    ++i;
    swap(a[i],a[r]);
    return i;
}

int select(int l, int r, int k)
{
    if (l >= r)
        return a[l];
    int p = partition(l, r);
    if (k == p)
        return a[k];
    else if(k > p)
        return select(p + 1, r, k);
    else
        return select(l, p - 1, k);
}

int main()
{
    int t, n;
    scanf("%d",&t);
    while (t--)
    {
        scanf("%d",&n);
        for (int i = 0; i < n; i++)
            scanf("%d",&a[i]);
        int x = select(0, n-1, n/2);
        int s = 0;
        for (int i = 0; i < n; i++)
        {
            s += abs(a[i] - x);
        }
        printf("%d\n",s);
    }
    return 0;
}

       了解快排的人对int (int l, int r) 这个函数很熟悉，因为这是在快排中用到的，它的作用是对数组的某一段选一个分界点，使得该点左边的数都不大于该点的数，右边的点不小于该点的数，也就是说我们通过一次调用这个函数确定一个数的位置，快排是将该点两边分别进行递归操作，时间复杂度为O(nlogn)，而select只是对一边进行递归操作（有点像二分的递归形式），所以时间复杂度仅为O(n)。

        其实还有时间复杂度更低的算法，划分树。。。   时间复杂度为log(n) 。。。。。   划分树的优点是可以对某个区间进行多次的查询，并不改变原序。

poj 2388

//poj 2388
#include <stdio.h>
#include <algorithm>
using namespace std;

const int maxn = 10005;

int a[maxn];

int partition(int l, int r)
{
    int x = a[r];
    int ol = l;
    for (int i = l; i < r; i++)
    {
        if (a[i] < x)
        {
            swap(a[ol], a[i]);
            ol++;
        }
    }
    swap(a[r], a[ol]);
    return ol;
}

int search(int l, int r, int k)
{
    int pos = partition(l, r);
    if (l == r)
        return a[l];
    if (k == pos)
        return a[k];
    else if (pos < k)
        return search(pos+1, r, k);
    else if (pos > k)
        return search(l, pos-1, k);
}

int main()
{
    int n;
    while (scanf("%d", &n) != EOF)
    {
        for (int i = 0; i < n; i++)
            scanf("%d",&a[i]);
        printf("%d\n",search(0, n-1, n/2));
    }
    return 0;
}