l**o
发帖数: 356 | 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********2
发帖数: 495 | 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******b
发帖数: 73 | | l**o
发帖数: 356 | 4 能不能详细说说呀
递归
【在 e********2 的大作中提到】
: 递归
:
: 个
| i*****h
发帖数: 1534 | | l********6
发帖数: 129 | | I******c
发帖数: 163 | 7 我的思路
[0,1,2,1,0] 从最右边的算起
第一个 是 0， 说明没有没有比它大的 所以这个数是 5
第二个 是 1， 说明有一个比他大，所以这个数是3 （4比它大）
第三个 是 2，说明有两个比他大，所以这个数是1 （2，4比它大）
类似。。。
结果应该是唯一的。 | l********6
发帖数: 129 | 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*******g
发帖数: 1335 | 9 还是用bst的方法，但是每个节点要维护它下面节点的个数，也许segment tree也能做。
思路：
root就是第一个节点。对数组从左到右遍历，假设当前值为N，意味着，当把这个数插
入bst时候，有N个数比他大，也就是说有N个数在它插入后在它右边。因为每个节点维
护了它下面节点的个数，因此可以通过bst以lgN时间找到该节点应该插入的位置，这个
比较复杂，程序不好写。
最后得到了bst，也就得到了数值。 | s*******n
发帖数: 305 | 10 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){
flag[j]=true;
A[i]=j+1;
break;
} else {
biggerLeft--;
}
}
}
return A;
} | | | r*******g
发帖数: 1335 | 11 还是用bst的方法，但是每个节点要维护它下面节点的个数，也许segment tree也能做。
思路：
root就是第一个节点。对数组从左到右遍历，假设当前值为N，意味着，当把这个数插
入bst时候，有N个数比他大，也就是说有N个数在它插入后在它右边。因为每个节点维
护了它下面节点的个数，因此可以通过bst以lgN时间找到该节点应该插入的位置，这个
比较复杂，程序不好写。
最后得到了bst，也就得到了数值。 | l********6
发帖数: 129 | 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******n
发帖数: 9344 | 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********6
发帖数: 129 | 14 history remove 复杂度多少
[在 longtian (有人的地方,就有江湖) 的大作中提到：]
：o(n)
：
：........... | l******n
发帖数: 9344 | 15 you are right,o(n^2)
【在 l********6 的大作中提到】
: history remove 复杂度多少
: [在 longtian (有人的地方,就有江湖) 的大作中提到：]
: ：o(n)
: ：
: ：...........
| y******g
发帖数: 4 | | y******g
发帖数: 4 | 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*********t
发帖数: 36 | 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********6
发帖数: 129 | 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**********9
发帖数: 54 | 20 其实就转化成每次都找剩下数字里面第ai大得数字
用一个二叉树存1 ～ n, 然后记录每个节点左右节点数
删除一个节点和修正左右节点数都是logn
所有算法是O(nlogn)
【在 l********6 的大作中提到】
: 想不出n平方以下的解法
|
|
