a******d
发帖数: 82 | 1 Merge List
Given two lists of items (list1 and list2), each list is sorted based on
the
weight in ascending order. Now merge list1 and list2.
return a sorted merged list.
条件:
If one item in list1 has the same id as an item in list2, combine these two
items into one item and the weight is sum of the two previous weights.
Class Item{
int id;
float weight;
}
剩的时间太少, 想了一会没想出来, 感觉应该有个O(n)的解法. 感觉应该是个merge
sort 的变形
请大家指教了, 谢谢 |
d*********e
发帖数: 352 | 2 要O（n）的话要用extra space吧
求大神给出 O（n） in place 解法 |
s***c
发帖数: 639 | 3 相同的weight就挪到连成第三个list，这样不需要额外空间，三个list一起merge，还
是O(n)
two
【在 a******d 的大作中提到】
: Merge List
: Given two lists of items (list1 and list2), each list is sorted based on
: the
: weight in ascending order. Now merge list1 and list2.
: return a sorted merged list.
: 条件:
: If one item in list1 has the same id as an item in list2, combine these two
: items into one item and the weight is sum of the two previous weights.
: Class Item{
: int id;
|
b***e
发帖数: 1419 | 4 没有O(n)的解法。可以把排序问题归结到这个问题上。即如果这个问题有O(n)的解则排
序有O(n)的解。
two
【在 a******d 的大作中提到】
: Merge List
: Given two lists of items (list1 and list2), each list is sorted based on
: the
: weight in ascending order. Now merge list1 and list2.
: return a sorted merged list.
: 条件:
: If one item in list1 has the same id as an item in list2, combine these two
: items into one item and the weight is sum of the two previous weights.
: Class Item{
: int id;
|
y***r
发帖数: 8 | 5
感觉你这个不能保证递增啊，比如说你先碰到2，和它配对的是10，然后碰到3，和它配
对的是4，那按你的办法就是12，7了 |
k*****u
发帖数: 7 | 6 请问用extra space的话，如何做到O(n)? 请问可以稍微讲一讲吗？
【在 d*********e 的大作中提到】
: 要O（n）的话要用extra space吧
: 求大神给出 O（n） in place 解法
|
C*7
发帖数: 234 | 7 恩，条件理解错了。。
【在 y***r 的大作中提到】
:
: 感觉你这个不能保证递增啊，比如说你先碰到2，和它配对的是10，然后碰到3，和它配
: 对的是4，那按你的办法就是12，7了
|
c*******t
发帖数: 123 | 8 用extra space的话，那太简单了。
按weight merge, 顺便加入
unordered_map map;
如果以前已经有这个id了，直接用指针去修改。
【在 k*****u 的大作中提到】
: 请问用extra space的话，如何做到O(n)? 请问可以稍微讲一讲吗？
|
b**********5
发帖数: 7881 | 9 return a sorted merged list.
你这个好像不return sorted merged list
【在 c*******t 的大作中提到】
: 用extra space的话，那太简单了。
: 按weight merge, 顺便加入
: unordered_map map;
: 如果以前已经有这个id了，直接用指针去修改。
|
j***y
发帖数: 5 | 10 最近看到一个湾区大弓有个面试算法的班，我刚才还发帖问，不知道有用没有？求大牛
推荐，求指点。 |
m*********g
发帖数: 170 | 11 ListNode
{
int id; //assuming be non-negative
float weight;
ListNode* next;
}
merge(ListNode* l1, ListNode* l2)
{
ListNode l1head, h2head, l3head;
l1head->next = l1;
l2head->next = l2;
ListNode* l3 = &h3head;
//use hashtable to keep track of the id->weight pair.
unordered_map m;
// populate with l1 list
while(l1 != NULL)
{
m.insert(pair(l1->id, l1->weight));
l1 = l1->next;
}
//check l2 list
while(l2 != NULL)
{
auto it = m.find(l2->id);
if(it != m.end())
{
// add it to l3
ListNode* temp = new ListNode(l1->id, l1->weight+l2->weight);
l3->next = temp;
l3 = l3->next;
//mark node from both l1 and l2
it->id = -1;
l2->id = -1;
}
l2 = l2->next;
}
// merge three List. skip ones with "-1" id.
} |
a******d
发帖数: 82 | 12 这个不能保证第三个链表也是递增吧, 这样merge 三个链表结果就不是递增啊.
【在 m*********g 的大作中提到】
: ListNode
: {
: int id; //assuming be non-negative
: float weight;
: ListNode* next;
: }
: merge(ListNode* l1, ListNode* l2)
: {
: ListNode l1head, h2head, l3head;
: l1head->next = l1;
|
n*******s
发帖数: 17267 | 13 Veli good, 是把相同ID的weight相加组成一个排好序的list再merge吧。
【在 s***c 的大作中提到】
: 相同的weight就挪到连成第三个list，这样不需要额外空间，三个list一起merge，还
: 是O(n)
:
: two
|
l*n
发帖数: 529 | 14 re这个。
具体原因在于类似这样的case：(a2, b4)跟(b5, a6)的merge。假设可以线性处理，拿
到(a2, b9)的结果后，遇到a6了需要跟a2组合，可结果a8小于b9，需要通过比较插入到
非末位位置，于是不可能做到O(n)。
【在 b***e 的大作中提到】
: 没有O(n)的解法。可以把排序问题归结到这个问题上。即如果这个问题有O(n)的解则排
: 序有O(n)的解。
:
: two
|
