p*****u
发帖数: 310 | 1 给定一个数字数组 (Let's call it count-array) ，其中每个元素是从末端数小于原
数组中该元素的个数。求原数组。原数组中元素是从1到n。
Example:
原数组 4,1, 3, 2
Count array 3, 0, 1, 0
求nlogn的算法。 |
g**********y
发帖数: 14569 | 2 这个O(n)就够了：
public int[] recover(int[] a) {
int[] s = new int[a.length];
ArrayList list = new ArrayList();
for (int i=0; i
for (int i=0; i
s[i] = list.remove(a[i]);
}
return s;
}
【在 p*****u 的大作中提到】
: 给定一个数字数组 (Let's call it count-array) ，其中每个元素是从末端数小于原
: 数组中该元素的个数。求原数组。原数组中元素是从1到n。
: Example:
: 原数组 4,1, 3, 2
: Count array 3, 0, 1, 0
: 求nlogn的算法。
|
s*****n
发帖数: 5488 | 3 list.remove的复杂度是多少？
【在 g**********y 的大作中提到】
: 这个O(n)就够了：
: public int[] recover(int[] a) {
: int[] s = new int[a.length];
: ArrayList list = new ArrayList();
: for (int i=0; i:
: for (int i=0; i: s[i] = list.remove(a[i]);
: }
:
|
a********m
发帖数: 15480 | 4 从头往后扫描。每个数字是当前可用数字从小到大排序的序号。 查找数字的部分可以
把所有数字做成一个bst. 叶结点是实际数字，其他结点是从这里往下的数字数目。 这
样查找数字是lgn. 每次去掉一个数字的时候更新路上的结点值。 |
r******n
发帖数: 170 | 5 贴个c++的版本:
void restore(int cnt_arr[], int orig_arr[], size_t size)
{
vector svec;
for(size_t i=0; i
svec.push_back(i+1);
for(size_t i=0; i
{
vector::iterator iter=svec.begin()+cnt_arr[i];
orig_arr[i]=*iter;
svec.erase(iter);
}
}
不知道能不能写的更简洁点？
【在 g**********y 的大作中提到】
: 这个O(n)就够了：
: public int[] recover(int[] a) {
: int[] s = new int[a.length];
: ArrayList list = new ArrayList();
: for (int i=0; i:
: for (int i=0; i: s[i] = list.remove(a[i]);
: }
:
|
P**********c
发帖数: 3417 | 6 就跟前面指出的，这个不是O(nlogn)。vector里remove一个element的复杂度是O(n), 所以这个算法是O(n^2). 另外你这个有序数组里找第k大的数写复杂了，应该就像刚来Java那个，const time.
另外我觉得G家的题目不能用STL做。否则它肯定会问你STL是怎么实现的，这个更容易出错。
【在 r******n 的大作中提到】
: 贴个c++的版本:
: void restore(int cnt_arr[], int orig_arr[], size_t size)
: {
: vector svec;
: for(size_t i=0; i: svec.push_back(i+1);
: for(size_t i=0; i: {
: vector::iterator iter=svec.begin()+cnt_arr[i];
: orig_arr[i]=*iter;
|
P**********c
发帖数: 3417 | 7 不明白，能否详细说说？
【在 a********m 的大作中提到】
: 从头往后扫描。每个数字是当前可用数字从小到大排序的序号。 查找数字的部分可以
: 把所有数字做成一个bst. 叶结点是实际数字，其他结点是从这里往下的数字数目。 这
: 样查找数字是lgn. 每次去掉一个数字的时候更新路上的结点值。
|
r******n
发帖数: 170 | 8 vector里面找数字那块是为了取对应的iterator,后面好用erase，不过也觉得不够简洁
漂亮，所以打算抛砖引玉。
假如这题是onsite用C/C++写的，我认为肯定是可以用stl的常见数据结构的，不然4，
50分钟怎么可能写个完整的结果出来？
所以这个算法是O(n^2). 另外你这个有序数组里找第k大的数写复杂了，应该就像刚
来Java那个，const time.
易出错。
【在 P**********c 的大作中提到】
: 就跟前面指出的，这个不是O(nlogn)。vector里remove一个element的复杂度是O(n), 所以这个算法是O(n^2). 另外你这个有序数组里找第k大的数写复杂了，应该就像刚来Java那个，const time.
: 另外我觉得G家的题目不能用STL做。否则它肯定会问你STL是怎么实现的，这个更容易出错。
|
s******n
发帖数: 226 | 9 我总么觉得解 不唯一呢， 如果最后一个是最大的（n），其他的都是0，不管你怎么排序 |
P**********c
发帖数: 3417 | 10 你没理解对题意吧。
0000对应的解肯定是1234
如果是1324，那就是0100
排序
【在 s******n 的大作中提到】
: 我总么觉得解 不唯一呢， 如果最后一个是最大的（n），其他的都是0，不管你怎么排序
|
|
|
s******n
发帖数: 226 | 11 你说的对 我以为和直方图面积一样的那种，遇到大的就停了
【在 P**********c 的大作中提到】
: 你没理解对题意吧。
: 0000对应的解肯定是1234
: 如果是1324，那就是0100
:
: 排序
|
d*******r
发帖数: 208 | 12 再循环里面erase，不小心很容易出bug
你这个循环里erase后，vector后面的数会补上来，应该加一个i--否者就跳过了一个数。
【在 r******n 的大作中提到】
: 贴个c++的版本:
: void restore(int cnt_arr[], int orig_arr[], size_t size)
: {
: vector svec;
: for(size_t i=0; i: svec.push_back(i+1);
: for(size_t i=0; i: {
: vector::iterator iter=svec.begin()+cnt_arr[i];
: orig_arr[i]=*iter;
|
d*******r
发帖数: 208 | 13 size 也会变化，要每次call
数。
【在 d*******r 的大作中提到】
: 再循环里面erase，不小心很容易出bug
: 你这个循环里erase后，vector后面的数会补上来，应该加一个i--否者就跳过了一个数。
|
d*******d
发帖数: 2050 | 14 这一段:
size_t j=0;
while(j
{
++j;
++iter;
}
直接写:
iter = iter + cnt_arr[i]
不就得了.vector的iterator是random access型的
【在 r******n 的大作中提到】
: 贴个c++的版本:
: void restore(int cnt_arr[], int orig_arr[], size_t size)
: {
: vector svec;
: for(size_t i=0; i: svec.push_back(i+1);
: for(size_t i=0; i: {
: vector::iterator iter=svec.begin()+cnt_arr[i];
: orig_arr[i]=*iter;
|
t**r
发帖数: 3428 | 15 OlogN
有点难度啊。
想半天还是不对，MARK一下 |
h*****g
发帖数: 312 | 16 题啥意思？ 能不能具体点？
【在 p*****u 的大作中提到】
: 给定一个数字数组 (Let's call it count-array) ，其中每个元素是从末端数小于原
: 数组中该元素的个数。求原数组。原数组中元素是从1到n。
: Example:
: 原数组 4,1, 3, 2
: Count array 3, 0, 1, 0
: 求nlogn的算法。
|
g***s
发帖数: 3811 | 17 //nlgn
public class BTree {
Node root;
public BTree(int n) {
root = makeTree(n, 0);
}
private Node makeTree(int number, int base) {
if (number == 0) return null;
Node node = new Node((number + 1) / 2 + base);
node.numOfLeftChildren = (number - 1) / 2;
node.left = makeTree(node.numOfLeftChildren, base);
node.right = makeTree(number / 2, node.value);
return node;
}
public Node remove(int index) {
return remove(root, index);
}
private Node remove(Node node, int index) {
if (node.numOfLeftChildren > index) {
//left
node.numOfLeftChildren--;
return remove(node.left, index);
}
if (node.numOfLeftChildren == index && !node.removed) {
//current
node.removed = true;
return node;
}
//right
return remove(node.right, index - node.numOfLeftChildren - (node.
removed ? 0 : 1));
}
public static int[] recover(int[] a) {
BTree list = new BTree(a.length);
int[] s = new int[a.length];
for (int i = 0; i < a.length; i++) {
s[i] = list.remove(a[i]).value;
}
return s;
}
static class Node {
int numOfLeftChildren;
int value;
Node left;
Node right;
boolean removed = false;
Node(int value) {
this.value = value;
}
}
public static void main(String[] args) {
List x = new ArrayList();
int NUM = 100;
for (int i = 0; i < NUM; i++) x.add(i + 1);
Collections.shuffle(x);
int[] a = makeSample(x.toArray());//new int[]{2,0,1,0};
System.out.println(Arrays.toString(x.toArray()));
System.out.println(Arrays.toString(a));
System.out.println(Arrays.toString(recover(a)));
}
private static int[] makeSample(Object[] x) {
int[] a = new int[x.length];
for (int i = 0; i < a.length; i++)
for (int j = i + 1; j < a.length; j++) {
if (((Integer) x[j]) < ((Integer) x[i])) a[i]++;
}
return a;
}
} |
g***s
发帖数: 3811 | |
s*****y
发帖数: 897 | 19 大牛，说一下你得code思路阿，看得不是很懂。
【在 g***s 的大作中提到】
: //nlgn
: public class BTree {
: Node root;
: public BTree(int n) {
: root = makeTree(n, 0);
: }
: private Node makeTree(int number, int base) {
: if (number == 0) return null;
: Node node = new Node((number + 1) / 2 + base);
: node.numOfLeftChildren = (number - 1) / 2;
|
s*****y
发帖数: 897 | 20 要是这个single link list改成hash_map+double linklist是不是就可以？
【在 s*****n 的大作中提到】
: list.remove的复杂度是多少？
|
|
|
a********m
发帖数: 15480 | 21 前面那个树开始是这样的，前面两行是计数，最后一行叶子是实际数字：
。。。。4
。。。2。。2
。。1。2。3。4
取走第一个4以后是
。。。。3
。。。2。。1
。。1。2。3
再取走1是
。。。。2
。。。1。。。1
。。。。2。3
关键是查现在的第几个数字需要lgn复杂度。所以很自然用树表示。 |
a********m
发帖数: 15480 | 22 hash没有排序功能。linklist都是n,不管single,double.
【在 s*****y 的大作中提到】
: 要是这个single link list改成hash_map+double linklist是不是就可以？
|
s**x
发帖数: 7506 | 23 这个怎么样？
也用 BST, every node has extra info to remember how many nodes on its left
subtree, and original index in the array. then scan the array from right to
left, so we can easily build a whole BST as the array tells us how many
nodes are less than a node.
at the end scan the BST by in-order and fill the numbers from 1 to n. |
a********m
发帖数: 15480 | 24 original index不用,用了反而不能lgn了,因为你需要更新it. 只用左子树叶子数目应
该可以。 |
s*****y
发帖数: 897 | 25 hash_map
double_linklist
delete value的时候，从hahs_map里面拿到要删除的node指针，然后从double_
linklist里面delete那个node,这不是o(1)?
【在 a********m 的大作中提到】
: hash没有排序功能。linklist都是n,不管single,double.
|
m****t
发帖数: 555 | 26 实际上，因为本题vector里的数据是序的，所以remove操作可以用binary search。
这样一来复杂度就是nlogn。
只不过这样一来我们不能使用标准的vector，需要自己 写code实现。
所以这个算法是O(n^2). 另外你这个有序数组里找第k大的数写复杂了，应该就像刚
来Java那个，const time.
易出错。
【在 P**********c 的大作中提到】
: 就跟前面指出的，这个不是O(nlogn)。vector里remove一个element的复杂度是O(n), 所以这个算法是O(n^2). 另外你这个有序数组里找第k大的数写复杂了，应该就像刚来Java那个，const time.
: 另外我觉得G家的题目不能用STL做。否则它肯定会问你STL是怎么实现的，这个更容易出错。
|
a********m
发帖数: 15480 | 27 这个linklist干啥用？ 比如现在hash里面有 3，4，5，7，9。我要第三大元素，怎么
拿到？
【在 s*****y 的大作中提到】
: hash_map
: double_linklist
: delete value的时候，从hahs_map里面拿到要删除的node指针，然后从double_
: linklist里面delete那个node,这不是o(1)?
|
g***s
发帖数: 3811 | 28 this BTree is a binary search tree, stored values from 1..n
Node
numOfLeftChildren is used to store the total number of nodes in the left(
all number are less than current value)
removed is used to mark it is removed
remove(index) : remove the index-th from the btree(just like list.remove(
index)). we use recursive method remove(Node node, int index) to do it.
check left/current/right.
【在 s*****y 的大作中提到】
: 大牛，说一下你得code思路阿，看得不是很懂。
|
m****t
发帖数: 555 | 29 总结一下，用一个vector存放1...n。
从头到尾扫描给定的数组，每得到一个值，从vector里删掉。因为vector里数据是有序
的，因此remove操作可以使用二分法，复杂度为O(logn).
这样本算法复杂度为O(nlogn). |
g***s
发帖数: 3811 | 30 check my codes. i did with a similar idea. but no original index needed.
to
【在 s**x 的大作中提到】
: 这个怎么样？
: 也用 BST, every node has extra info to remember how many nodes on its left
: subtree, and original index in the array. then scan the array from right to
: left, so we can easily build a whole BST as the array tells us how many
: nodes are less than a node.
: at the end scan the BST by in-order and fill the numbers from 1 to n.
|
|
|
g***s
发帖数: 3811 | 31 "因此remove操作可以使用二分法" how?
【在 m****t 的大作中提到】
: 总结一下，用一个vector存放1...n。
: 从头到尾扫描给定的数组，每得到一个值，从vector里删掉。因为vector里数据是有序
: 的，因此remove操作可以使用二分法，复杂度为O(logn).
: 这样本算法复杂度为O(nlogn).
|
s**x
发帖数: 7506 | 32 i c, but removing has overhead too.
【在 g***s 的大作中提到】
: check my codes. i did with a similar idea. but no original index needed.
:
: to
|
a********m
发帖数: 15480 | 33 vec的删除操作复杂度n
【在 m****t 的大作中提到】
: 实际上，因为本题vector里的数据是序的，所以remove操作可以用binary search。
: 这样一来复杂度就是nlogn。
: 只不过这样一来我们不能使用标准的vector，需要自己 写code实现。
:
: 所以这个算法是O(n^2). 另外你这个有序数组里找第k大的数写复杂了，应该就像刚
: 来Java那个，const time.
: 易出错。
|
a********m
发帖数: 15480 | 34 那个overhead是lgn.符合要求。
【在 s**x 的大作中提到】
: i c, but removing has overhead too.
|
g***s
发帖数: 3811 | 35 Did you check my codes? remove is log N
【在 s**x 的大作中提到】
: i c, but removing has overhead too.
|
d*******r
发帖数: 208 | 36 orig: 4, 1, 3, 2
count: 3, 0, 1, 0
use a priority queue, pq, element comparison based on count array value
first,
count array index second
1. insert all count array elements into pq
2. extract min from pq until empty, fill the corresponding position of orig
array with increasing values
ex.
3 0 1 0
0 1 2 3
pq order would be. 1 3 2 0
then orig[1] = 1, orig[3] = 2, orig[2] = 3, orig[0] = 4
【在 p*****u 的大作中提到】
: 给定一个数字数组 (Let's call it count-array) ，其中每个元素是从末端数小于原
: 数组中该元素的个数。求原数组。原数组中元素是从1到n。
: Example:
: 原数组 4,1, 3, 2
: Count array 3, 0, 1, 0
: 求nlogn的算法。
|
s*****y
发帖数: 897 | 37 我想错了,thanks。
【在 a********m 的大作中提到】
: 这个linklist干啥用？ 比如现在hash里面有 3，4，5，7，9。我要第三大元素，怎么
: 拿到？
|
d*******r
发帖数: 208 | 38 c++ code:
typedef struct E {
int i;
int v;
E(int i_, int v_) : i(i_), v(v_) {}
} E;
struct Comp {
bool operator()(const E& a, const E& b) {
if (a.v > b.v) { return true; }
else if (a.v < b.v) { return false; }
else { return a.i > b.i; }
}
};
void recover(int count[], int orig[], int n) {
std::priority_queue, Comp> pq;
for (int i=0;i
E e(i, count[i]);
pq.push(e);
}
int k=1;
while(!pq.empty()) {
E e = pq.top();
orig[e.i] = k++;
pq.pop();
}
}
orig
【在 d*******r 的大作中提到】
: orig: 4, 1, 3, 2
: count: 3, 0, 1, 0
: use a priority queue, pq, element comparison based on count array value
: first,
: count array index second
: 1. insert all count array elements into pq
: 2. extract min from pq until empty, fill the corresponding position of orig
: array with increasing values
: ex.
: 3 0 1 0
|
g***s
发帖数: 3811 | 39 It is incorrect. e.g.
[1, 0, 0]
【在 d*******r 的大作中提到】
: c++ code:
: typedef struct E {
: int i;
: int v;
: E(int i_, int v_) : i(i_), v(v_) {}
: } E;
: struct Comp {
: bool operator()(const E& a, const E& b) {
: if (a.v > b.v) { return true; }
: else if (a.v < b.v) { return false; }
|
j**l
发帖数: 2911 | 40 可以化归为这样一道题：
设计一个有序的数据结构，最初里头有自然数1到n这n个元素，
随后这些元素可以被删除，但剩下元素仍然保持有序。
要求实现方法GetKthElement(int k)和RemoveKthElemenet(int k)，使得它们在任意时
刻都不超过O(lgN), N为当前的元素个数, 1 <= k <= N
感觉要结合BST之类 |
|
|
j**l
发帖数: 2911 | 41 以前有道题是, 如何在log(N)时间找到BST的第i个元素。方法就是每个节点附加左子树
的元素个数和右子树的元素个数。 |
d*******r
发帖数: 208 | 42 you are right.
再想想
【在 g***s 的大作中提到】
: It is incorrect. e.g.
: [1, 0, 0]
|
l***i
发帖数: 1309 | 43 you can also use fenwick tree, which is simple to implement. |
j**l
发帖数: 2911 | 44 Should be:
Node remove(Node node, int index)
{
if (node.numOfLeftChildren >= index)
{
// left
node.numOfLeftChildren--;
return remove(node.left, index);
}
else if (node.numOfLeftChildren + 1 == index && !node.removed)
{
// current
node.removed = true;
return node;
}
else
{
// right
return remove(node.right, index - node.numOfLeftChildren - (node.
removed ? 0 : 1));
}
}
【在 g***s 的大作中提到】
: //nlgn
: public class BTree {
: Node root;
: public BTree(int n) {
: root = makeTree(n, 0);
: }
: private Node makeTree(int number, int base) {
: if (number == 0) return null;
: Node node = new Node((number + 1) / 2 + base);
: node.numOfLeftChildren = (number - 1) / 2;
|
g***s
发帖数: 3811 | 45 为什么改？ 不觉得原来有问题。改了反而错了。例如index=0
Should be:Node remove(Node node, int index){
★ Sent from iPhone App: iReader Mitbbs Lite 7.20
【在 j**l 的大作中提到】
: Should be:
: Node remove(Node node, int index)
: {
: if (node.numOfLeftChildren >= index)
: {
: // left
: node.numOfLeftChildren--;
: return remove(node.left, index);
: }
: else if (node.numOfLeftChildren + 1 == index && !node.removed)
|
j**l
发帖数: 2911 | 46 I see, I assume index start from 1, while you assume index start from 0
My case should use:
s[i] = list.remove(a[i] + 1).value, since a[i] start from 0
【在 g***s 的大作中提到】
: 为什么改？ 不觉得原来有问题。改了反而错了。例如index=0
:
: Should be:Node remove(Node node, int index){
: ★ Sent from iPhone App: iReader Mitbbs Lite 7.20
|
l*****e
发帖数: 1374 | 47 其实就是Dynamic order statistics
大家可以参考算法导论14.1内容:
需要在O(lgn)时间内取得第i大元素，同时调整树的时间也应该在O(lgn) |
n********y
发帖数: 66 | 48 Idea
3 0 1 0
Step 1: use any nlgn Alg to sort and memorize old position
3 1 0 0
Step 2: count same from left to right O(n)
1 1 2
Step 3: place # (in this order: 2 1 1) O(n)
index: 0 1 2 3
1
1 2
3 1 2
4 3 1 2
Step 4: access using old position |
k****n
发帖数: 369 | 49 There is a straightforward solution:
Suppose we have a set of 1 to n, then from the 1st element of the count-
array c[], a[i] is the c[i]'th element left in the set, when we move forward
, we also need to delete a[i] from the set.
So the problem is, how to find and delete k'th element in lgn time.
This is traditional. A BST with subtree size should be enough.
【在 p*****u 的大作中提到】
: 给定一个数字数组 (Let's call it count-array) ，其中每个元素是从末端数小于原
: 数组中该元素的个数。求原数组。原数组中元素是从1到n。
: Example:
: 原数组 4,1, 3, 2
: Count array 3, 0, 1, 0
: 求nlogn的算法。
|
k****n
发帖数: 369 | 50 wrong, in a sorted vector, it is true that find k can be achieved in O(lgn),
but remove it need O(n).
【在 m****t 的大作中提到】
: 总结一下，用一个vector存放1...n。
: 从头到尾扫描给定的数组，每得到一个值，从vector里删掉。因为vector里数据是有序
: 的，因此remove操作可以使用二分法，复杂度为O(logn).
: 这样本算法复杂度为O(nlogn).
|
|
|
a**********2
发帖数: 340 | 51 可以用merge sort(desc)吧
思路更简单：
merge 的时候对于前半部分的元素i和后半部分的元素j
如果input[i] >= input[j] 那么i对应的元素的count就应该增加 high-j+1
这样每次merge的时候都保证后半部分比他小的元素被加进来了
worst case也是O(nlogn） |
q****x
发帖数: 7404 | 52 你说的是逆问题吧。
【在 a**********2 的大作中提到】
: 可以用merge sort(desc)吧
: 思路更简单：
: merge 的时候对于前半部分的元素i和后半部分的元素j
: 如果input[i] >= input[j] 那么i对应的元素的count就应该增加 high-j+1
: 这样每次merge的时候都保证后半部分比他小的元素被加进来了
: worst case也是O(nlogn）
|
q****x
发帖数: 7404 | 53 我觉得这个是正解。
【在 l*****e 的大作中提到】
: 其实就是Dynamic order statistics
: 大家可以参考算法导论14.1内容:
: 需要在O(lgn)时间内取得第i大元素，同时调整树的时间也应该在O(lgn)
|
g***s
发帖数: 3811 | 54 要编一个Dynamic order statistics的删除算法，那可远远超过了一般面试难度啊。即
使是acm/icpc，或者IIO都会尽量避免去做这个麻烦的算法。
【在 q****x 的大作中提到】
: 我觉得这个是正解。
|
q****x
发帖数: 7404 | 55 其实思路上比较容易，因为都是现成的。
你老的解法是定制简化版，更牛。
另外我想不用删除吧。插入也行。
【在 g***s 的大作中提到】
: 要编一个Dynamic order statistics的删除算法，那可远远超过了一般面试难度啊。即
: 使是acm/icpc，或者IIO都会尽量避免去做这个麻烦的算法。
|
a**********2
发帖数: 340 | 56 这样做应该没错吧？
【在 q****x 的大作中提到】
: 你说的是逆问题吧。
|
a**********2
发帖数: 340 | 57 没有仔细验证
typedef pair PAIR;
void getCountArray(vector input)
{
int len = input.size();
vector count(len, 0);
vector input1;
int i;
for( i = 0; i < len; i++)
input1.push_back(PAIR(input[i],i));
vector tmp( len, PAIR(0,0));
MergeSort(input1, 0, len-1, tmp, count);
for( i = 0; i < len; i++)
cout << count[i] ;
cout << endl;
}
void Merge(vector& input, int low, int mid, int high,vector&
tmp
, vector& count)
{
int i = low;
int j = mid;
int k = low;
while( i < mid && j <= high)
{
if(input[i].first >= input[j].first)
{
count[input[i].second] += high-j+1;
tmp[k++] = input[i++];
}
else
{
tmp[k++] = input[j++];
}
}
while( i < mid)
tmp[k++] = input[i++];
while( j <= high)
tmp[k++] = input[j++];
for( i = low; i <= high; i++)
{
input[i] = tmp[i];
}
}
void MergeSort(vector& input, int low, int high,vector& tmp,
vector& count)
{
if( low >= high) return;
int mid = low + (high-low)/2;
MergeSort(input, low, mid, tmp, count);
MergeSort(input, mid+1, high,tmp, count);
Merge(input, low, mid+1, high, tmp, count);
} |
e*******r
发帖数: 47 | 58 看IT面经：
http://haiwaibbs.com/forum.php?mod=forumdisplay&fid=47
【在 p*****u 的大作中提到】
: 给定一个数字数组 (Let's call it count-array) ，其中每个元素是从末端数小于原
: 数组中该元素的个数。求原数组。原数组中元素是从1到n。
: Example:
: 原数组 4,1, 3, 2
: Count array 3, 0, 1, 0
: 求nlogn的算法。
|
d*******l
发帖数: 338 | 59 我记得POJ上有一道一模一样的题，是典型的线段树/树状数组的题，线段树可以做到
nlogn，树状数组nlog^2n。我应该A掉了，方法就是用线段树维护一个区间内还剩下的
点的个数。 |
