Honestly, I couldn’t solve this one on my first attempt. I only figured it out after reading someone else’s approach, and I still made boundary errors multiple times. Embarrassing.
Let me explain the approach.
My initial idea was: merge sort the two arrays, then output array[median]. But clearly this has a time complexity higher than $O(\log(m+n))$ – it’s about $O(m+n)$.
The time complexity constraint is what makes this problem frustrating.
OK, looking at the conditions again: two already sorted arrays, and the required time complexity is logarithmic. What does that remind you of? Binary search?
But how do you apply binary search to this problem? There’s a bit of math involved.
For the detailed derivation, see: http://blog.chinaunix.net/uid-28490468-id-3576490.html
I had seen another blog post about this before, but I can’t find it anymore. Oh well.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
| ListNode *l;
class Solution {
public:
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
// Note: The Solution object is instantiated only once and is reused by each test case.
l1 = Reverse(l1);
l2 = Reverse(l2);
ListNode *ans = NULL;
ListNode *ansbackup = NULL;
int sum = 0;
int now = 0;
int next = 0;
while(true)
{
if(l1 == NULL || l2 == NULL)
break;
sum = l1->val + l2->val+next;
now = sum % 10;
next = sum / 10;
ListNode *tmp = new ListNode(now);
if(ans == NULL)
{
ans = tmp;
ansbackup = ans;
}
else
{
ans->next = tmp;
ans = ans->next;
}
l1 = l1->next;
l2 = l2->next;
}
if(l1 != NULL)
{
while(true)
{
if(l1 == NULL) break;
sum = l1->val + next;
now = sum % 10;
next = sum / 10;
ListNode *tmp = new ListNode(now);
ans->next = tmp;
ans = ans->next;
l1 = l1->next;
}
}
if(l2 != NULL)
{
while(true)
{
if(l2 == NULL) break;
sum = l2->val + next;
now = sum % 10;
next = sum / 10;
ListNode *tmp = new ListNode(now);
ans->next = tmp;
ans = ans->next;
l2 = l2->next;
}
}
if(next != 0)
{
ListNode *tmp = new ListNode(next);
ans->next = tmp;
ans = ans->next;
}
return ansbackup;
}
ListNode *Reverse(ListNode *l)
{
ListNode *before;
ListNode *now;
ListNode *next;
if(l->next == NULL)
return l;
before = l;
now = l->next;
while(now == NULL)
{
next = now->next;
now->next = before;
before = now;
now = next;
}
return before;
}
};
|