LeetCode 004 [Median of Two Sorted Arrays]

Problem

Median of Two Sorted Arrays
There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Solution

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
90
91
92
93
94
95
96
97
98
99
100
101
102
class Solution
{
public:
double findMedianSortedArrays(int A[], int m, int B[], int n)
{

int beginA = 0, endA = m - 1, beginB = 0, endB = n - 1;
return findMedian(A, beginA, endA, B, beginB, endB);
}
double findMedian(int A[], int beginA, int endA, int B[], int beginB, int endB)
{

if ((endA - beginA + 1) <= 2 && (endB - beginB + 1) <= 2)
{
return finalfindMedian(A, beginA, endA, B, beginB, endB);
}
int middleA = (beginA + endA) / 2;
int middleB = (beginB + endB) / 2;
if ((endA - beginA + 1) <= 2)
{
if ((endB - beginB + 1) % 2 == 1)
{
beginB = middleB - 1;
endB = middleB + 1;
}
else
{
beginB = middleB - 1;
endB = middleB + 2;
}
return finalfindMedian(A, beginA, endA, B, beginB, endB);
}
if ((endB - beginB + 1) <= 2)
{
if ((endA - beginA + 1) % 2 == 1)
{
beginA = middleA - 1;
endA = middleA + 1;
}
else
{
beginA = middleA - 1;
endA = middleA + 2;
}
return finalfindMedian(B, beginB, endB, A, beginA, endA);
}
int medianA, medianB;
int length;
medianA = A[middleA];
medianB = B[middleB];
if (medianA >= medianB)
{
length = (endA - middleA) < (middleB - beginB) ? (endA - middleA) : (middleB - beginB);
length = length < (middleA - beginA) ? length : (middleA - beginA);
return findMedian(A, beginA, endA - length, B, beginB + length, endB);
}
else
{
length = (endB - middleB) < (middleA - beginA) ? (endB - middleB) : (middleA - beginA);
length = length < (middleB - beginB) ? length : (middleB - beginB);
return findMedian(A, beginA + length, endA, B, beginB, endB - length);
}
}
double finalfindMedian(int A[], int beginA, int endA, int B[], int beginB, int endB)
{

int i, j, k = 0, temp;
int num[10];
int count = endA - beginA + 1 + endB - beginB + 1;
for (i = beginA; i <= endA; i++)
{
num[k] = A[i];
k++;
}
for (i = beginB; i <= endB; i++)
{
num[k] = B[i];
k++;
}
if (count == 1)
{
return (double)num[0];
}
for (i = 0; i < count; i++)
{
for (j = i; j < count; j++)
{
if (num[j] < num[i])
{
temp = num[j];
num[j] = num[i];
num[i] = temp;
}
}
}
if (count % 2 == 0)
{
return (double)(((double)num[count / 2 - 1] + (double)num[count / 2]) / 2);
}
else
{
return (double)num[count / 2];
}
}
};

Comment

  1. 代码有冗余
  2. 复杂度达到要求