国内推出北美留学生pre course了 - 未名空间MITBBS历史存档

国内推出北美留学生pre course了# Joke - 肚皮舞运动

g*n2013-06-28 07:06

1 楼

You are given two array, first array contain integer which represent heights
of persons and second array contain how many persons in front of him are
standing who are greater than him in term of height and forming a queue. Ex
A: 3 2 1
B: 0 1 1
It means in front of person of height 3 there is no person standing, person
of height 2 there is one person in front of him who has greater height then
he, similar to person of height 1. Your task to arrange them
Ouput should be.
3 1 2
Here, 3 is at front, 1 has 3 in front ,2 has 1 and 3 in front.
另外补充一个例子：
A=5 10 15 4 13 6 3 12
B=0 0 0 1 1 1 2 2
输出是： 5 4 3 10 6 15 13 12
希望能有快过O(n^2)的解法。请大牛们赐教~

w*s2013-06-28 07:06

2 楼

【#人人热门状态#】发现蓝翔有两个月的摄影班，三个月的缝纫班，两个月的美容班，
三个月的美发班，两个月的调酒班，两个半月的糕点班，三个月的烹饪综合班，一个半
月的修电动车班，两个月的修电脑班……好想去学啊啊啊如果掌握了这些技术好像就能
幸福生活的样子（via 人人网張从火 Antifin）

z*g2013-06-28 07:06

3 楼

另外补充一个例子：
A=5 10 15 4 13 6 3 12
B=0 0 0 1 1 1 2 2
输出是： 5 4 3 10 6 15 13 12
这个例子是对的吗？好像不对啊？

heights
Ex
person
then

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

: You are given two array, first array contain integer which represent heights
: of persons and second array contain how many persons in front of him are
: standing who are greater than him in term of height and forming a queue. Ex
: A: 3 2 1
: B: 0 1 1
: It means in front of person of height 3 there is no person standing, person
: of height 2 there is one person in front of him who has greater height then
: he, similar to person of height 1. Your task to arrange them
: Ouput should be.
: 3 1 2

m*y2013-06-28 07:06

4 楼

修电动车班：《
这不是给北美留学生推出的吧？不过，老汉还一直想到community college去学修车。

r*a2013-06-28 07:06

5 楼

如果不是要求严格最坏情况小于平方的话，支持下标访问的跳表可能是此题在面试里最
好写的方法了，平均复杂度应该是O(nlogn)。
http://en.wikipedia.org/wiki/Skip_list#Indexable_skiplist

heights
Ex
person
then

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

: You are given two array, first array contain integer which represent heights
: of persons and second array contain how many persons in front of him are
: standing who are greater than him in term of height and forming a queue. Ex
: A: 3 2 1
: B: 0 1 1
: It means in front of person of height 3 there is no person standing, person
: of height 2 there is one person in front of him who has greater height then
: he, similar to person of height 1. Your task to arrange them
: Ouput should be.
: 3 1 2

Y*Z2013-06-28 07:06

6 楼

我想参加缝纫班。

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

: 【#人人热门状态#】发现蓝翔有两个月的摄影班，三个月的缝纫班，两个月的美容班，
: 三个月的美发班，两个月的调酒班，两个半月的糕点班，三个月的烹饪综合班，一个半
: 月的修电动车班，两个月的修电脑班……好想去学啊啊啊如果掌握了这些技术好像就能
: 幸福生活的样子（via 人人网張从火 Antifin）

b*e2013-06-28 07:06

7 楼

Do the n*log(n) sorting first, then the question is converted to
reconstructing permutation from an inversion sequence. The definition of
inversion sequence can be found here:
http://en.wikipedia.org/wiki/Inversion_(discrete_mathematics)#C
There are well known n*log(n) algorithms for this reconstruction.

heights
Ex
person
then

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

: You are given two array, first array contain integer which represent heights
: of persons and second array contain how many persons in front of him are
: standing who are greater than him in term of height and forming a queue. Ex
: A: 3 2 1
: B: 0 1 1
: It means in front of person of height 3 there is no person standing, person
: of height 2 there is one person in front of him who has greater height then
: he, similar to person of height 1. Your task to arrange them
: Ouput should be.
: 3 1 2

t*t2013-06-28 07:06

8 楼

个人不愧是第一名校

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

: 【#人人热门状态#】发现蓝翔有两个月的摄影班，三个月的缝纫班，两个月的美容班，
: 三个月的美发班，两个月的调酒班，两个半月的糕点班，三个月的烹饪综合班，一个半
: 月的修电动车班，两个月的修电脑班……好想去学啊啊啊如果掌握了这些技术好像就能
: 幸福生活的样子（via 人人网張从火 Antifin）

b*e2013-06-28 07:06

9 楼

skip list可以用tree来实现。那样的话time complexity就严格的是O(n*log(n))了。

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

: 如果不是要求严格最坏情况小于平方的话，支持下标访问的跳表可能是此题在面试里最
: 好写的方法了，平均复杂度应该是O(nlogn)。
: http://en.wikipedia.org/wiki/Skip_list#Indexable_skiplist
:
: heights
: Ex
: person
: then

r*32013-06-28 07:06

10 楼

没有inter course的，就算不得上档次

l*e2013-06-28 07:06

11 楼

请问这个是谁家的面试题目？

heights
Ex
person
then

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

: You are given two array, first array contain integer which represent heights
: of persons and second array contain how many persons in front of him are
: standing who are greater than him in term of height and forming a queue. Ex
: A: 3 2 1
: B: 0 1 1
: It means in front of person of height 3 there is no person standing, person
: of height 2 there is one person in front of him who has greater height then
: he, similar to person of height 1. Your task to arrange them
: Ouput should be.
: 3 1 2

d*n2013-06-28 07:06

12 楼

不错
烹饪是必须的

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

: 【#人人热门状态#】发现蓝翔有两个月的摄影班，三个月的缝纫班，两个月的美容班，
: 三个月的美发班，两个月的调酒班，两个半月的糕点班，三个月的烹饪综合班，一个半
: 月的修电动车班，两个月的修电脑班……好想去学啊啊啊如果掌握了这些技术好像就能
: 幸福生活的样子（via 人人网張从火 Antifin）

B*g2013-06-28 07:06

13 楼

谢谢，只会n^2，看来还要学习呀

【在 b***e 的大作中提到】

: skip list可以用tree来实现。那样的话time complexity就严格的是O(n*log(n))了。

f*42013-06-28 07:06

14 楼

似乎可以用线段树，树结点(a,b)代表以a开头有b个位置可用。每次确定一个元素的位
置（只能在叶子节点中），再分裂该结点。举一个有代表性的例子：
排序后：A[]={1,2,3,4,5,6}，B[]={2,4,0,2,0,0}
线段树一开始只有 (0,6)，A[0]的占据的位置是2，分裂为
(0,5)
/ \
(0,2) (3,3)
再依次对A[1],A[2]...确定位置并分裂

b*e2013-06-28 07:06

15 楼

基本就是这个思路。

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

: 似乎可以用线段树，树结点(a,b)代表以a开头有b个位置可用。每次确定一个元素的位
: 置（只能在叶子节点中），再分裂该结点。举一个有代表性的例子：
: 排序后：A[]={1,2,3,4,5,6}，B[]={2,4,0,2,0,0}
: 线段树一开始只有 (0,6)，A[0]的占据的位置是2，分裂为
: (0,5)
: / \
: (0,2) (3,3)
: 再依次对A[1],A[2]...确定位置并分裂

c*p2013-06-28 07:06

16 楼

也可以用BST保存所有的位置吧。每个节点加一个counter，计数以该节点为根的子树
节点数。
这样找位置的时候就可以根据counter确定。如果一个位置确定了，就把对应的节点去
掉。同时，调整祖先节点的counter. 每次查找和调整的复杂度都是 log(n).

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

: 似乎可以用线段树，树结点(a,b)代表以a开头有b个位置可用。每次确定一个元素的位
: 置（只能在叶子节点中），再分裂该结点。举一个有代表性的例子：
: 排序后：A[]={1,2,3,4,5,6}，B[]={2,4,0,2,0,0}
: 线段树一开始只有 (0,6)，A[0]的占据的位置是2，分裂为
: (0,5)
: / \
: (0,2) (3,3)
: 再依次对A[1],A[2]...确定位置并分裂

u*n2013-06-28 07:06

17 楼

怎么没看太懂题目啊？output具体是要根据array2来arrange array1吗？那补充的例子
该如何解释啊？求指点

R*i2013-06-28 07:06

18 楼

My solution is:
1) Sort the first array, O(nlog(n));
In the given example, the sort array is: 3, 4, 5, 6, 10, 12, 13, 15
2) Reconstruct the output based on the second array, but from the end of the
second array. In the given example, the last item is 2. So the item in the
output array should be 12 because 12 is before 13 and 15. 13 and 15 are the
two numbers which are greater than 12. Then we can reconstruct the second
last element which is 2 in the second array. Because 12 is taken out, so 10
should take the position, and so on.

x*82013-06-28 07:06

19 楼

2nd example answer seems incorrect, it should be :
3,4,15,5,6,13,10,12 ?

heights
Ex
person
then

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

: You are given two array, first array contain integer which represent heights
: of persons and second array contain how many persons in front of him are
: standing who are greater than him in term of height and forming a queue. Ex
: A: 3 2 1
: B: 0 1 1
: It means in front of person of height 3 there is no person standing, person
: of height 2 there is one person in front of him who has greater height then
: he, similar to person of height 1. Your task to arrange them
: Ouput should be.
: 3 1 2

y*k2013-06-28 07:06

20 楼

The idea is good but Step 2) needs to be improved. After removing some
element from the array, it is not easy to get the k-th element anymore. You
may want to change the data structure.

the
the
the
10

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

: My solution is:
: 1) Sort the first array, O(nlog(n));
: In the given example, the sort array is: 3, 4, 5, 6, 10, 12, 13, 15
: 2) Reconstruct the output based on the second array, but from the end of the
: second array. In the given example, the last item is 2. So the item in the
: output array should be 12 because 12 is before 13 and 15. 13 and 15 are the
: two numbers which are greater than 12. Then we can reconstruct the second
: last element which is 2 in the second array. Because 12 is taken out, so 10
: should take the position, and so on.
:

R*i2013-06-28 07:06

21 楼

You are right. I think we should modified BST which is suggested by chump.

You

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

: The idea is good but Step 2) needs to be improved. After removing some
: element from the array, it is not easy to get the k-th element anymore. You
: may want to change the data structure.
:
: the
: the
: the
: 10

o*n2013-06-28 07:06

22 楼

一开始没用BST，做出来费老劲了。BST就容易太多了。看看对吗？ ;)
A=[5, 10, 15, 4, 13, 6, 3, 12]
B=[0, 0, 0, 1, 1, 1, 2, 2]
class tree:
def __init__(self, data):
self.data= data
self.left= None
self.right= None
n=len(A)
rootlst=[]
def build_tree(node, t): #Build BST tree
if node.data > t.data :
if t.right == None:
t.right = node
return
else: build_tree(node, t.right)
if node.data <= t.data :
if t.left == None:
t.left = node
return
else: build_tree(node, t.left)
def print_tree(t): # print out the tree in preorder
print t.data
if t.left !=None:
print_tree(t.left)
if t.right !=None:
print_tree(t.right)
for i in range(n):
if B[i]==0:
rootlst.append(A[i])
d=sorted(rootlst)[0]
root=tree(d)
for i in A[1::]:
build_tree(tree(i),root)
print_tree(root)

o*n2013-06-28 07:06

23 楼

结果。
5
4
3
10
6
15
13
12
不需要考虑其他的，直接建树，打印。

d*n2013-06-28 07:06

24 楼

这个算法行不行，基本上和上面的同学说的差不多。
第一步，把身高数组和b数组，一起按身高数组排序。
第二步，从最小的element开始，reconstruct 新的数组。
第一步是O(nlgn).第二步，最坏是O(n^2)。（当b全为0）时。
以下是程序。
#include
#include
#include
using namespace std;
struct mypair {
int a;
int b;
mypair(int c,int d) {a=c;b=d;}
friend bool operator};
bool operatorreturn (p1.a}
vector heightcomp(vector& a,vector& b) {
int i,k,j,n,m;
n=a.size();
vector vt;
for(i=0;imypair* pa=new mypair(a[i],b[i]);
vt.push_back(*pa);
}
sort(vt.begin(),vt.end());
vector tmp(n,0);
for(i=0;ik=vt[i].b;//k cells space should be reserved before ith element;
m=0;
j=0;
for(j=0;jif(tmp[j]==0) m++;//count the total empty cells before ith element;
if(m==k+1) break;//if we had enough empty cells
}
tmp[j]=vt[i].a; //set the k+1th empty cell to the value of ith element
}
return tmp;
}

heights
Ex
person
then

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

: You are given two array, first array contain integer which represent heights
: of persons and second array contain how many persons in front of him are
: standing who are greater than him in term of height and forming a queue. Ex
: A: 3 2 1
: B: 0 1 1
: It means in front of person of height 3 there is no person standing, person
: of height 2 there is one person in front of him who has greater height then
: he, similar to person of height 1. Your task to arrange them
: Ouput should be.
: 3 1 2

c*e2013-06-28 07:06

25 楼

1. 以A中数字为key排序（B随之排序）
2. 建树，把A中数字从大到小插入到书中，每个node记录左右子树的大小leftsize，
rightsize：
现在插入数字a with b
1. 如果leftsize+1>=b，递归插入右子树且b=b-leftsize-1（已有leftsize+1数在a
之前）
2. 否则，插入左子树。
3. 若插入的子树为空，则插入到这个位置。
3. 中序打印

e*l2013-06-28 07:06

26 楼

为什么前面的解法都怎么复杂？假设输入已经根据身高从大到小排序
A={15, 13, 12, 10, 6, 5, 4, 3}
B={ 0, 1, 2, 0, 1, 0, 1, 2}
开一个空链表C，依次把身高h插入C的B[h]位置，结束。简单吧？
ArrayList C = new ArrayList();
for(int i=0;iC.insert(B[A[i]], A[i]);
按顺序输出C：{5,4,3,10,6,15,13,12}

l*n2013-06-28 07:06

27 楼

这个解释的确直观，虽然是o(n^2)的。

【在 e***l 的大作中提到】

: 为什么前面的解法都怎么复杂？假设输入已经根据身高从大到小排序
: A={15, 13, 12, 10, 6, 5, 4, 3}
: B={ 0, 1, 2, 0, 1, 0, 1, 2}
: 开一个空链表C，依次把身高h插入C的B[h]位置，结束。简单吧？
: ArrayList C = new ArrayList();
: for(int i=0;i: C.insert(B[A[i]], A[i]);
: 按顺序输出C：{5,4,3,10,6,15,13,12}

p*e2013-06-28 07:06

28 楼

两步：（1）先把A从大到小排序，O(nlogn)，（2）在sorted A里，从左往右，对应的B
里的值就是那个数的index。第二步用c++ list比较好做一些。

heights
Ex
person
then

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

: You are given two array, first array contain integer which represent heights
: of persons and second array contain how many persons in front of him are
: standing who are greater than him in term of height and forming a queue. Ex
: A: 3 2 1
: B: 0 1 1
: It means in front of person of height 3 there is no person standing, person
: of height 2 there is one person in front of him who has greater height then
: he, similar to person of height 1. Your task to arrange them
: Ouput should be.
: 3 1 2