请教个问题，不知发这里是否合适？谢谢# CS - 计算机科学
m*n
1 楼
☆─────────────────────────────────────☆
babyfacenan (黑土) 于 (Sun Mar 30 19:26:16 2008) 提到:
Given two sorted arrays A, B, find the m pairs with the smallest sums.
比如 A={1, 2, 4, 5, 6}, B={3, 5, 7, 9}
m=3
那么Results就是(1, 3),(2, 3),(1, 5)
看了以前大家的讨论
不知道最好的方法complexity是多少呀？
☆─────────────────────────────────────☆
coal (煤炭) 于 (Sun Mar 30 19:28:59 2008) 提到:
O(m)吧
☆─────────────────────────────────────☆
MCWY (牧场物语) 于 (Sun Mar 30 22:31:40 2008) 提到:
O(m*n)
n=min(len(A),len(B))
☆─────────────
babyfacenan (黑土) 于 (Sun Mar 30 19:26:16 2008) 提到:
Given two sorted arrays A, B, find the m pairs with the smallest sums.
比如 A={1, 2, 4, 5, 6}, B={3, 5, 7, 9}
m=3
那么Results就是(1, 3),(2, 3),(1, 5)
看了以前大家的讨论
不知道最好的方法complexity是多少呀？
☆─────────────────────────────────────☆
coal (煤炭) 于 (Sun Mar 30 19:28:59 2008) 提到:
O(m)吧
☆─────────────────────────────────────☆
MCWY (牧场物语) 于 (Sun Mar 30 22:31:40 2008) 提到:
O(m*n)
n=min(len(A),len(B))
☆─────────────
