六一快乐 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

六一快乐

六一快乐# Joke - 肚皮舞运动

B*12011-06-01 07:06

1 楼

Give an unsorted array find count of pairs of numbers[a,b] where a > b and b
comes after a in the array.
Eg. {8,3,6,10,5}
the count of such numbers is 5. i.e. (8,3), (8,6), (8,5), (6,5) and (10,5)
觉得这题跟amazon的这个很像，大家有没有这个感觉啊？
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(n)
use of extra space allowed.

z*n2011-06-01 07:06

2 楼

节日快乐！

m*t2011-06-01 07:06

3 楼

就是这道题。只能达到 O(nlgn)
http://stackoverflow.com/questions/3836767/interview-question-r

b
equal

【在 B*******1 的大作中提到】

: Give an unsorted array find count of pairs of numbers[a,b] where a > b and b
: comes after a in the array.
: Eg. {8,3,6,10,5}
: the count of such numbers is 5. i.e. (8,3), (8,6), (8,5), (6,5) and (10,5)
: 觉得这题跟amazon的这个很像，大家有没有这个感觉啊？
: 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(n)

k*u2011-06-01 07:06

4 楼

跟着排

节日快乐！

【在 z****n 的大作中提到】

: 节日快乐！

g*y2011-06-01 07:06

5 楼

这个是求总和，比Amazon的简单。要是Amazon那个O(n)可解，这个也可以。但是这个有
O(n)解，不表明Amazon那个也有。

b
equal

【在 B*******1 的大作中提到】

d*d2011-06-01 07:06

6 楼

use a bst, each node contain an extra field which hold the number of nodes
in the tree.

h*62011-06-01 07:06

7 楼

用二叉索引树很容易的吧。

d*d2011-06-01 07:06

8 楼

不一样,但是差不多.

g*y2011-06-01 07:06

9 楼

O(nlogn)不难，但是肯定没有O(n)的解吗？

【在 h**6 的大作中提到】

: 用二叉索引树很容易的吧。

r*g2011-06-01 07:06

10 楼

hi
你们的思路是，对unsorted array做bst？然后呢？

【在 g**********y 的大作中提到】

: O(nlogn)不难，但是肯定没有O(n)的解吗？

g*y2011-06-01 07:06

11 楼

CLRS习题2.4-d
public class InversionCount {
public int count(int[] a) {
return mergeSort(a, 0, a.length - 1);
}

private int mergeSort(int[] a, int p, int r) {
if (p >= r) return 0;
int q = (p + r) / 2;
int c1 = mergeSort(a, p, q);
int c2 = mergeSort(a, q+1, r);
return c1 + c2 + merge(a, p, q, r);
}

private int merge(int[] a, int p, int q, int r) {
int[] t = new int[r - p + 1];
int count = 0;

int i = p;
int j = q+1;
int k = 0;
while (i<=q && j<=r) {
if (a[i] <= a[j]) {
t[k++] = a[i++];
}
else {
t[k++] = a[j++];
count += q-i+1;
}
}

while (i<=q) t[k++] = a[i++];
while (j<=r) t[k++] = a[j++];

for (i=p; i<=r; i++) a[i] = t[i-p];
return count;
}
}

【在 r*******g 的大作中提到】

: hi
: 你们的思路是，对unsorted array做bst？然后呢？

s*f2011-06-01 07:06

12 楼

一个unsorted array建立BST的worst time complexity是O(n^2)吧？

g*y2011-06-01 07:06

13 楼

hans说的应该是B-tree, 不是bst.

【在 s***f 的大作中提到】

: 一个unsorted array建立BST的worst time complexity是O(n^2)吧？

r*g2011-06-01 07:06

14 楼

man，我是想问思路啊，你给我的是mergesort的实现。
mergesort和这个题什么关系？

【在 g**********y 的大作中提到】

: CLRS习题2.4-d
: public class InversionCount {
: public int count(int[] a) {
: return mergeSort(a, 0, a.length - 1);
: }
:
: private int mergeSort(int[] a, int p, int r) {
: if (p >= r) return 0;
: int q = (p + r) / 2;
: int c1 = mergeSort(a, p, q);

g*y2011-06-01 07:06

15 楼

无语，你不能读读程序吗？如果不愿意读，你运行一下程序也行啊。

【在 r*******g 的大作中提到】

: man，我是想问思路啊，你给我的是mergesort的实现。
: mergesort和这个题什么关系？

r*g2011-06-01 07:06

16 楼

哈哈，不好意思，刚才看的太不仔细了，你是对的，原来就是mergesort的时候不断求
和就行了，这个想法很好。thanks

【在 g**********y 的大作中提到】

: 无语，你不能读读程序吗？如果不愿意读，你运行一下程序也行啊。

d*y2011-06-01 07:06

17 楼

看了你的程序想起来以前做过这题。
可能是放在merge sort后面的练习里面的。
忘了可以这么做这个题了。

【在 g**********y 的大作中提到】

: 无语，你不能读读程序吗？如果不愿意读，你运行一下程序也行啊。

g*i2011-06-01 07:06

18 楼

bst怎么做? unbalance bst的话10和5在两个不同的tree里,怎么找到这对pair?

【在 d*******d 的大作中提到】

: use a bst, each node contain an extra field which hold the number of nodes
: in the tree.

d*d2011-06-01 07:06

19 楼

struct Node{
int v;
int count;
Node * left;
Node * right;
Node(int _v):v(_v), count(1), left(0), right(0){}
};
void insert(Node * & root, int v, int & c){
if( root == 0){
root = new Node(v);
return;
}
root->count++;
if( root->v == v){
if(root->right)
c = c + root->right->count;
}else if( v < root->v){
insert(root->left, v, c);
c = c + root->count - root->left->count;
}else{
insert(root->right, v, c);
}
return;
}
int find(int * a, int n){
Node * root = 0;
int c = 0;
for(int i = 0; i< n; i++){
insert( root, a[i], c);
}
return c;
}

【在 g*****i 的大作中提到】

: bst怎么做? unbalance bst的话10和5在两个不同的tree里,怎么找到这对pair?

B*12011-06-01 07:06

20 楼

这个worse case 还是o(n2)吧？