Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1022760
  • 博文数量: 242
  • 博客积分: 10209
  • 博客等级: 上将
  • 技术积分: 3028
  • 用 户 组: 普通用户
  • 注册时间: 2008-03-12 09:27
文章分类

全部博文(242)

文章存档

2014年(1)

2013年(1)

2010年(51)

2009年(65)

2008年(124)

我的朋友

分类: C/C++

2010-07-15 17:54:12

AMAZON Interview Question:

You have an array like ar[]= {1,3,2,4,5,4,2}. You need to create
another array ar_low[] such that ar_low[i] = number of elements lower
than or equal to ar[i] in ar[i+1:n-1].
So the output of above should be {0,2,1,2,2,1,0}

Time complexity : O(nlogn)
use of extra space allowed.

解:首先想到的是最直接的方法,
    for(i=0;i        for(j=i+1;j            if(ar[i] >= ar[j])
                ar_low[i]++;

   但这个方法的复杂度为O(n^2)。

   若需满足算法复杂度O(nlogn)的要求,可以使用二叉查找树,从ar数组的最后一个元素开始,逐步将ar数组元素插入到二叉查找树中,插入的过程中,即可完成对ar_low数组的赋值,由于构建二叉查找树的复杂度为O(nlogn), 整个过程的算法复杂的也为O(nlogn)。
二叉查找树构建 平均算法复杂度为O(nlogn),但最坏算法复杂度为O(n^2)。

这里先用二叉查找树实现如下:
struct BSTnode
{
    int key;
    int index;
    struct BSTnode *left;
    struct BSTnode *right;
    struct BSTnode *parent;
};

struct BSTnode * BSTinsert(struct BSTnode *root,struct BSTnode *node)
{
    struct BSTnode *pointer = root;
    struct BSTnode *back =    NULL;

    while(pointer != NULL)
    {
        back = pointer;
        if(node->key >= pointer->key)
            pointer = pointer->left;
        else
            pointer = pointer->right;
    }

    node->parent = back;

    if(back ==  NULL)
        root = node;
    else if(node->key >= back->key)
        back->left = node;
    else
        back->right = node;

    return root;
}

void Free(struct BSTnode *root)
{
    if(root != NULL)
    {
        Free(root->left);
        Free(root->right);
        free(root);
    }
   
}
int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);

    int n = 7;
    int ar[] = {1,3,2,4,5,4,2};
    int *ar_low = (int *)calloc(n,sizeof(int));
    struct BSTnode *root = NULL;

    for(int i=n-1;i>=0;i--)
    {
        struct BSTnode *node = (struct BSTnode *)malloc(sizeof(struct BSTnode));
        node->key = ar[i];
        node->index = i;
        node->left = node->right = NULL;
        node->parent = NULL;
        root = BSTinsert(root,node);
        if(node->parent!=NULL)
        {
            if(node->parent->left == node)
                ar_low[i] = ar_low[node->parent->index] + 1;
            else
                ar_low[i] = ar_low[node->parent->index];
        }else
            ar_low[i] = 0;

    }

    for(int i=0;i        printf("%d ",ar_low[i]);
    printf("\n");

    free(ar_low);
    Free(root);

}

阅读(1112) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~