xindoo is
always here

第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;
}

     


赞(0) 打赏
未经允许不得转载:XINDOO » 第K小数 uva 10041 – Vito’s Family poj 2388 Who’s in the Middle
分享到: 更多 (0)

评论 抢沙发

xindoo

联系我联系我们

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏