k**********a
发帖数: 255 | 1 有一整数的集合 （set） 用双向链表实现 而且双向链表是已经从小到大排序的
现在要实现一种并集的算法 把集合A B求并集 （如上所述 A B 都已经排序好）算法时
间复杂度要求 O（m ＋n） m 为A的元素数目 n 为B的元素数目
想了半天 不知道如何实现这个算法
为消除歧义 补充一点要求 集合中不可以出现重复的元素 合并好的集合也是必须排序好的 |
t****t
发帖数: 6806 | 2 两个排好序的链表合并不会?
【在 k**********a 的大作中提到】
: 有一整数的集合 （set） 用双向链表实现 而且双向链表是已经从小到大排序的
: 现在要实现一种并集的算法 把集合A B求并集 （如上所述 A B 都已经排序好）算法时
: 间复杂度要求 O（m ＋n） m 为A的元素数目 n 为B的元素数目
: 想了半天 不知道如何实现这个算法
: 为消除歧义 补充一点要求 集合中不可以出现重复的元素 合并好的集合也是必须排序好的
|
k**********a
发帖数: 255 | 3 合并不难 但是合并了有duplicate的元素啊
而且要求合并之后的集合也是排序好的
好像必须是双向链表才可以 单向链表做不到
【在 t****t 的大作中提到】
: 两个排好序的链表合并不会?
|
t****t
发帖数: 6806 | 4 看清楚了, 我说的是合并, 不是把两个链表头尾相连
【在 k**********a 的大作中提到】
: 合并不难 但是合并了有duplicate的元素啊
: 而且要求合并之后的集合也是排序好的
: 好像必须是双向链表才可以 单向链表做不到
|
k**********a
发帖数: 255 | 5 我只想出了一个时间复杂度是O（m×n）的想法
请指教
【在 t****t 的大作中提到】
: 看清楚了, 我说的是合并, 不是把两个链表头尾相连
|
t****t
发帖数: 6806 | 6 ....
google merge sorted list
顺便说, 实在不能理解这么intuitive的事情会有人想不出来
【在 k**********a 的大作中提到】
: 我只想出了一个时间复杂度是O（m×n）的想法
: 请指教
|
k**********a
发帖数: 255 | 7 脑筋短路了 想出来了
两个链表从最小的开始 每次都比较两个链表的最小的 看两个之中谁更小 把更小的放
到新生成的链表中 |
t****t
发帖数: 6806 | 8 这不是挺对的么
怎么可能有人想不出来
几岁的小屁孩, 叫他把两堆排好的扑克牌整理一下, 他肯定也能想到这个算法
想不到的肯定是弱智
【在 k**********a 的大作中提到】
: 脑筋短路了 想出来了
: 两个链表从最小的开始 每次都比较两个链表的最小的 看两个之中谁更小 把更小的放
: 到新生成的链表中
|
k**********a
发帖数: 255 | 9 当初没想出来因为题目有个要求有迷惑性 本来以为他要求不可以生成新的链表 只能把
一个向另一个里边插 要插肯定就是想不出来
【在 t****t 的大作中提到】
: 这不是挺对的么
: 怎么可能有人想不出来
: 几岁的小屁孩, 叫他把两堆排好的扑克牌整理一下, 他肯定也能想到这个算法
: 想不到的肯定是弱智
|
t****t
发帖数: 6806 | 10 先不说把一个往另一个里面插, 和生成一个新的有什么区别
我就问你, 如果要求把一个往另一个里面插, 有什么做不到的么?
【在 k**********a 的大作中提到】
: 当初没想出来因为题目有个要求有迷惑性 本来以为他要求不可以生成新的链表 只能把
: 一个向另一个里边插 要插肯定就是想不出来
|
s*x
发帖数: 3328 | 11 你确认你想出来的那个是O(m x n)不是O(m+n)?
【在 k**********a 的大作中提到】
: 我只想出了一个时间复杂度是O（m×n）的想法
: 请指教
|
