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
|
