再来问道面经题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

再来问道面经题

再来问道面经题# JobHunting - 待字闺中

l*o2015-10-26 07:10

1 楼

给一个array比如[4,2,1,3,5],根据这个array现在我们能有了一个新的array => 每个
数是在原array里, 在它左边的所有比它大的number的个数,就是[0,1,2,1,0]. 题目是
现在给了这个[0,1,2,1,0]要求原array, 原来array的range是1~n
谢谢

e*22015-10-26 07:10

2 楼

递归

个

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

: 给一个array比如[4,2,1,3,5],根据这个array现在我们能有了一个新的array => 每个
: 数是在原array里, 在它左边的所有比它大的number的个数,就是[0,1,2,1,0]. 题目是
: 现在给了这个[0,1,2,1,0]要求原array, 原来array的range是1~n
: 谢谢

d*b2015-10-26 07:10

3 楼

1
21
321
4213
42135

l*o2015-10-26 07:10

4 楼

能不能详细说说呀

递归

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

: 递归
:
: 个

i*h2015-10-26 07:10

5 楼

没看懂题目，囧

l*62015-10-26 07:10

6 楼

想不出n平方以下的解法

I*c2015-10-26 07:10

7 楼

我的思路
[0,1,2,1,0] 从最右边的算起
第一个是 0，说明没有没有比它大的所以这个数是 5
第二个是 1，说明有一个比他大，所以这个数是3 （4比它大）
第三个是 2，说明有两个比他大，所以这个数是1 （2，4比它大）
类似。。。
结果应该是唯一的。

l*62015-10-26 07:10

8 楼

拿个数组装54321
从后往前第一个是0，就是5，remove，数组里面还剩下4321
接下来是1，就是3，remove，数组里还剩下421
接下来是2，就是1，remove，数组里还剩下42
接下来是1，就是2，remove，数组里还剩下4
接下来是0，就是4，remove，数组空
但是复杂度不知道该怎么办。。。

【在 I******c 的大作中提到】

: 我的思路
: [0,1,2,1,0] 从最右边的算起
: 第一个是 0，说明没有没有比它大的所以这个数是 5
: 第二个是 1，说明有一个比他大，所以这个数是3 （4比它大）
: 第三个是 2，说明有两个比他大，所以这个数是1 （2，4比它大）
: 类似。。。
: 结果应该是唯一的。

r*g2015-10-26 07:10

9 楼

还是用bst的方法，但是每个节点要维护它下面节点的个数，也许segment tree也能做。
思路：
root就是第一个节点。对数组从左到右遍历，假设当前值为N，意味着，当把这个数插
入bst时候，有N个数比他大，也就是说有N个数在它插入后在它右边。因为每个节点维
护了它下面节点的个数，因此可以通过bst以lgN时间找到该节点应该插入的位置，这个
比较复杂，程序不好写。
最后得到了bst，也就得到了数值。

s*n2015-10-26 07:10

10 楼

public int[] recovery(int[] B){
int len = B.length;
int[] A = new int[len];
boolean[] flag = new boolean[len];

for(int i=0; iint biggerLeft = B[i];
for(int j=0; jif(flag[j]==true) continue;
if(biggerLeft==0){
flag[j]=true;
A[i]=j+1;
break;
} else {
biggerLeft--;
}
}
}
return A;
}

r*g2015-10-26 07:10

11 楼

l*62015-10-26 07:10

12 楼

复杂度不还是n平方么？？

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

: public int[] recovery(int[] B){
: int len = B.length;
: int[] A = new int[len];
: boolean[] flag = new boolean[len];
:
: for(int i=0; i: int biggerLeft = B[i];
: for(int j=0; j: if(flag[j]==true) continue;
: if(biggerLeft==0){

l*n2015-10-26 07:10

13 楼

o(n)
def recover( thelist ):
n = len(thelist)
origlist = range(1,n+1)
history = range(1,n+1)
for i in range(n-1,-1,-1):
if (i == n-1):
origlist[i] = n - thelist[i]
history.remove(origlist[i])
else:
index = i - thelist[i]
origlist[i] = history[index]
history.remove(origlist[i])
return(origlist)
def main():
thelist = [0,1,2,1,0]
print(recover(thelist))
if __name__=="__main__":
main()

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

: 复杂度不还是n平方么？？

l*62015-10-26 07:10

14 楼

history remove 复杂度多少
[在 longtian (有人的地方,就有江湖) 的大作中提到：]
：o(n)
：
：...........

l*n2015-10-26 07:10

15 楼

you are right,o(n^2)

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

: history remove 复杂度多少
: [在 longtian (有人的地方,就有江湖) 的大作中提到：]
: ：o(n)
: ：
: ：...........

y*g2015-10-26 07:10

16 楼

test

y*g2015-10-26 07:10

17 楼

How about this solution?
#include
#include
#include
using namespace std;
void print(vector &A) {
cout << "[";
int counter = 0;

for_each(A.begin(), A.end(), [&](int i) {
if (counter++) {
cout << ", ";
}
cout << i;
});

cout << "]" << endl;
};
vector solve(vector &A) {
vector result;

if (!A.empty()) {
vector candidates;
for (int i = (int)A.size(); i >=1; --i) {
candidates.emplace_back(i);
}

//print(candidates);

for_each(A.rbegin(), A.rend(), [&](int i) {
//cout << i << endl;
result.emplace_back(candidates[i]);
candidates.erase(candidates.begin()+i);
});
}

reverse(result.begin(), result.end());

return result;
};
int main() {
// your code goes here
vector A{0,1,2,1,0};

vector result;

result = solve(A);
print(result);

return 0;
}

s*t2015-10-26 07:10

18 楼

用 set (set is BST) 做
count array is [0, 1, 2, 1, 0]
1. base array is iset = [1, 2,, 3, 4, 5]
4th count = 0 -> (4-0) = 4th largest
4th val = iset.begin()+ 4 = 5
iset.erase(5)
2. array -> 1, 2, 3, 4
3rd count -> (3-1) =2nd largest
3rd val = iset.begin()+2 =3
iset.erase(3)
result: original array = 4 2 1 3 5
O(nlogn)

l*62015-10-26 07:10

19 楼

不知道你说的set是不是STL里的set，不过想提醒你一下，STL的set的iterator是
bidirectional iterator不是randomaccessiterator，namely，是不支持类似begin()
+ 4这种操作的

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

: 用 set (set is BST) 做
: count array is [0, 1, 2, 1, 0]
: 1. base array is iset = [1, 2,, 3, 4, 5]
: 4th count = 0 -> (4-0) = 4th largest
: 4th val = iset.begin()+ 4 = 5
: iset.erase(5)
: 2. array -> 1, 2, 3, 4
: 3rd count -> (3-1) =2nd largest
: 3rd val = iset.begin()+2 =3
: iset.erase(3)

p*92015-10-26 07:10

20 楼

其实就转化成每次都找剩下数字里面第ai大得数字
用一个二叉树存1 ～ n, 然后记录每个节点左右节点数
删除一个节点和修正左右节点数都是logn
所有算法是O(nlogn)

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

: 想不出n平方以下的解法