B*******1
发帖数: 2454 | 1 似乎在本版没有见过
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.
这题可以O(n)吗？ |
d*******d
发帖数: 2050 | 2 我觉得这种数组题最难.总是在很小的空间中弄来弄去的搞些小tricky.
不像图论题那样大开大阖. |
g**********y
发帖数: 14569 | 3 No. If u can, generate this array; do it reverse way, generate another array
. With these two, you can sort the array in O(n).
equal
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 B*******1 的大作中提到】
: 似乎在本版没有见过
: 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.
: 这题可以O(n)吗？
|
B*******1
发帖数: 2454 | 4 可否详细点？
thanks
array
【在 g**********y 的大作中提到】
: No. If u can, generate this array; do it reverse way, generate another array
: . With these two, you can sort the array in O(n).
:
: equal
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
|
g**********y
发帖数: 14569 | 5 For each element, you know exactly how many elements lower than it, from
those two generated arrays.
Create a empty array, fill all elements in right position, that's sorted
array.
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 B*******1 的大作中提到】
: 可否详细点？
: thanks
:
: array
|
S**I
发帖数: 15689 | 6 If the elements in the array are integers and have upper and lower bounds,
it can be solved in linear time by using counting sort; otherwise, I doubt
there is a linear solution.
equal
【在 B*******1 的大作中提到】
: 似乎在本版没有见过
: 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.
: 这题可以O(n)吗？
|
r*******g
发帖数: 1335 | 7 even with sorted array, how to solve lz's problem?
【在 S**I 的大作中提到】
: If the elements in the array are integers and have upper and lower bounds,
: it can be solved in linear time by using counting sort; otherwise, I doubt
: there is a linear solution.
:
: equal
|
c******o
发帖数: 534 | 8 怎么solve？
count sort好像不太行。不知道怎么更新count。
【在 S**I 的大作中提到】
: If the elements in the array are integers and have upper and lower bounds,
: it can be solved in linear time by using counting sort; otherwise, I doubt
: there is a linear solution.
:
: equal
|
c*********n
发帖数: 1371 | 9 如果数值的范围不大，或者对space没有要求，我觉得这个题可以O(n)：
1， 用类似counting sort的第一步算出包含每个数值 elements lower
than or equal的数组A（[0,1,3,4,6,7].
2, if(ar.length==0) return null;
3, else if(ar.length==1) return {0}
4, else{
ar_low[0]=0;
for i from 1 to ar.length){
ar_low[i]=A[ar[i]];
(for j from ar[i] to A.length-1){
A[j]--;
}
}
5, 如果ar中有负数， 那就设一个最小负数到0的位移量 |
c******o
发帖数: 534 | 10 2个for 循环是 O（n）？
【在 c*********n 的大作中提到】
: 如果数值的范围不大，或者对space没有要求，我觉得这个题可以O(n)：
: 1， 用类似counting sort的第一步算出包含每个数值 elements lower
: than or equal的数组A（[0,1,3,4,6,7].
: 2, if(ar.length==0) return null;
: 3, else if(ar.length==1) return {0}
: 4, else{
: ar_low[0]=0;
: for i from 1 to ar.length){
: ar_low[i]=A[ar[i]];
: (for j from ar[i] to A.length-1){
|
|
|
c******o
发帖数: 534 | 11 for i from 1 to ar.length){
ar_low[i]=A[ar[i]];
(for j from ar[i] to A.length-1){
A[j]--;
}
如果每个值都不同，这个j不是要n到1么，
2个for循环。
复杂度是 O（n^2）啊
difference
【在 S**I 的大作中提到】
: If the elements in the array are integers and have upper and lower bounds,
: it can be solved in linear time by using counting sort; otherwise, I doubt
: there is a linear solution.
:
: equal
|
c******o
发帖数: 534 | 12 减一个不对。
【在 S**I 的大作中提到】
: If the elements in the array are integers and have upper and lower bounds,
: it can be solved in linear time by using counting sort; otherwise, I doubt
: there is a linear solution.
:
: equal
|
S**I
发帖数: 15689 | 13 you're right, let me think again.
【在 c******o 的大作中提到】
: 减一个不对。
|
m**q
发帖数: 189 | 14 O(nlgn)应该可行
1) 用merge sort，在merge的过程中计算ar_low[]的值。
2) 或者先记录下每个元素在数组中的index，然后用稳定排序
sort原数组，然后从头遍历数组，用一个set维护ar[0]
~ar[i-1]的元素在原数组中的index，对于每一个元素
用原来的index在set中二分查找，并把原来的index
插入到set中
equal
【在 B*******1 的大作中提到】
: 似乎在本版没有见过
: 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.
: 这题可以O(n)吗？
|
B*******1
发帖数: 2454 | 15 可以把每一步运行的结果列一下嘛？看得不是很清楚。 |
m****t
发帖数: 555 | 16 从partial ranking得到原来的数组，O(n)做不到，应该是O(nlgn).这个以前本版有这
个题的讨论。
array
【在 g**********y 的大作中提到】
: No. If u can, generate this array; do it reverse way, generate another array
: . With these two, you can sort the array in O(n).
:
: equal
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
|
g**********y
发帖数: 14569 | 17 这个题特殊，按照Bayesian说的，如果有那种算法，你可以O(n)时间生成左右partial
ranking, 合起来就是ranking了，也就把数组sort好了, 理论上，这是O(n)做不到的（
用比较的办法的话）。
【在 m****t 的大作中提到】
: 从partial ranking得到原来的数组，O(n)做不到，应该是O(nlgn).这个以前本版有这
: 个题的讨论。
:
: array
|
m****t
发帖数: 555 | 18 partial ranking =〉global ranking 可以 O(n)做到吗？我觉得不可能。如果可以的话，那么
partial ranking =〉global ranking => original array就可以在O(n)做到，这是不可能
的。
partial
【在 g**********y 的大作中提到】
: 这个题特殊，按照Bayesian说的，如果有那种算法，你可以O(n)时间生成左右partial
: ranking, 合起来就是ranking了，也就把数组sort好了, 理论上，这是O(n)做不到的（
: 用比较的办法的话）。
|
t********3
发帖数: 567 | 19 这个就是 counting sort 的变体啊，只要里面的数值范围有限，可以 做到的，
counting sort本来就是O（n）的排序 |
B*******1
发帖数: 2454 | |
|
|
m****t
发帖数: 555 | 21 counting sort得到的是global ranking, 得不到本题这种partial ranking.
可能没有O(n)算法
【在 t********3 的大作中提到】
: 这个就是 counting sort 的变体啊，只要里面的数值范围有限，可以 做到的，
: counting sort本来就是O（n）的排序
|
c*****m
发帖数: 315 | 22 这个应该有O(N） 的算法， 那个COUNTING SORT 的思路应该是对的。 |
g**********y
发帖数: 14569 | 23 那你写一个出来让我们看看？
【在 c*****m 的大作中提到】
: 这个应该有O(N） 的算法， 那个COUNTING SORT 的思路应该是对的。
|
c*****m
发帖数: 315 | 24 从题意来看，这个题肯定是假设KEY 的范围很有限，但是数很多， 也就是N>>K， 所以
ASYMPTOTICALLY, 复杂度应该是O(N)。
我猜解题的关键是用一个好的数据结构做BUCKET 来计数，可以COMBINE HASHMAP 和
LINKED LIST。稍后贴上我的代码。 |
c*****m
发帖数: 315 | 25 我可能想太简单了，也可能理解错了，假设KEY 是从1到K连续分布的，复杂度可以是O(
N*K)，不知道能不能把K 看成常数。嘿嘿。
（发现我的代码和coolaladdin 是一回事）。
public int [] partial_count(int [] arr){
int [] count=new int [K];
int [] partial_count=new int [arr.length];
//.......initialize to zeros
for(int i=arr.length-1;i>=0;i++)
int v=arr[i];
partial_count[i]=count[v-1];
for(int j=v-1;j
count[j]++;
}
return partial_count;
} |
m****t
发帖数: 555 | 26 counting sort的条件是 k=O(n), k不是一个常数。所以你的算法是O(n^2).
O(
【在 c*****m 的大作中提到】
: 我可能想太简单了，也可能理解错了，假设KEY 是从1到K连续分布的，复杂度可以是O(
: N*K)，不知道能不能把K 看成常数。嘿嘿。
: （发现我的代码和coolaladdin 是一回事）。
: public int [] partial_count(int [] arr){
: int [] count=new int [K];
: int [] partial_count=new int [arr.length];
: //.......initialize to zeros
: for(int i=arr.length-1;i>=0;i++)
: int v=arr[i];
: partial_count[i]=count[v-1];
|
