c**y 发帖数: 172 | 1 给定一个数组a(所有元素都是unique),找到所有的pair(a_i, a_j)符合条件:i < j
并且 a[i] > a[j]。
brutal force的解法是O(n^2),n是元素的个数。
如何提到到O(n log n)? |
r*******e 发帖数: 7583 | 2 counting inversions, 类似于merge sort
http://www.geeksforgeeks.org/counting-inversions/
j
【在 c**y 的大作中提到】 : 给定一个数组a(所有元素都是unique),找到所有的pair(a_i, a_j)符合条件:i < j : 并且 a[i] > a[j]。 : brutal force的解法是O(n^2),n是元素的个数。 : 如何提到到O(n log n)?
|
c**y 发帖数: 172 | 3 正解,膜拜大牛
【在 r*******e 的大作中提到】 : counting inversions, 类似于merge sort : http://www.geeksforgeeks.org/counting-inversions/ : : j
|
s**x 发帖数: 7506 | |
d****n 发帖数: 233 | 5 This is the sub problem of another one discussed here: http://www.mitbbs.com/article_t1/JobHunting/32401359_0_4.html
There is another solution by using Binary search insert method. Take a look
at:
http://codeanytime.blogspot.com/2013/05/score-of-racers.html
【在 s**x 的大作中提到】 : Mark
|
n****i 发帖数: 9 | 6 有O(n)的解法啊,正向扫描把当前最大的放到stack,然后反向扫描,满足条件的stack
.pop
j
【在 c**y 的大作中提到】 : 给定一个数组a(所有元素都是unique),找到所有的pair(a_i, a_j)符合条件:i < j : 并且 a[i] > a[j]。 : brutal force的解法是O(n^2),n是元素的个数。 : 如何提到到O(n log n)?
|
u******g 发帖数: 89 | 7 虽然没仔细想你哪里不对了,不过貌似已知最好的算法是 O(n lg lg n)。。
linear的只有近似算法。。
stack
【在 n****i 的大作中提到】 : 有O(n)的解法啊,正向扫描把当前最大的放到stack,然后反向扫描,满足条件的stack : .pop : : j
|
d****n 发帖数: 233 | 8 Can you give more details?
stack
【在 n****i 的大作中提到】 : 有O(n)的解法啊,正向扫描把当前最大的放到stack,然后反向扫描,满足条件的stack : .pop : : j
|
w**********0 发帖数: 214 | 9 5,4,3,2,1
这种descending order的, 输出组合就有n^2种,怎么可能nlogn 找出来 |
s*****n 发帖数: 5488 | 10 多亏看了大牛这篇,今天电面就用到了。
尼玛15分钟写一个merge sort变种。只有敲键盘的时间啊。太变态了。
【在 r*******e 的大作中提到】 : counting inversions, 类似于merge sort : http://www.geeksforgeeks.org/counting-inversions/ : : j
|