s******d
发帖数: 61 | 1 We have two sorted int arrays
a[] --> size N --> contains N elements
b[] --> size 2N --> contains N elements, and N vacant locations
Write an algorithm of complexity O(n) such that b[] contains elements of a[]
and b[] in ascending order.
merge()能保证复杂度o(n)吗?......sorting还没复习,稀里糊涂的现在==|| |
P**********c
发帖数: 3417 | 2 当然，扫一遍就是O(n)
[]
【在 s******d 的大作中提到】
: We have two sorted int arrays
: a[] --> size N --> contains N elements
: b[] --> size 2N --> contains N elements, and N vacant locations
: Write an algorithm of complexity O(n) such that b[] contains elements of a[]
: and b[] in ascending order.
: merge()能保证复杂度o(n)吗?......sorting还没复习,稀里糊涂的现在==||
|
d***n
发帖数: 65 | 3 应该还有个条件吧，比如不使用额外空间之类的。否则太trivial了。 |
M**u
发帖数: 10158 | 4 从屁股到头归并丫
[]
【在 s******d 的大作中提到】
: We have two sorted int arrays
: a[] --> size N --> contains N elements
: b[] --> size 2N --> contains N elements, and N vacant locations
: Write an algorithm of complexity O(n) such that b[] contains elements of a[]
: and b[] in ascending order.
: merge()能保证复杂度o(n)吗?......sorting还没复习,稀里糊涂的现在==||
|
f*******t
发帖数: 7549 | 5 我记得答案说得很清楚啊，从后往前并，时间复杂度跟普通的merge sorted数组一样是O(n)
，显然不消耗额外空间 |
h**********8
发帖数: 267 | 6 mark
[]
【在 s******d 的大作中提到】
: We have two sorted int arrays
: a[] --> size N --> contains N elements
: b[] --> size 2N --> contains N elements, and N vacant locations
: Write an algorithm of complexity O(n) such that b[] contains elements of a[]
: and b[] in ascending order.
: merge()能保证复杂度o(n)吗?......sorting还没复习,稀里糊涂的现在==||
|
