¶LeetCode - 4 : Median of Two Sorted Arrays
There are two sorted arrays nums1 and nums2 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)).
You may assume nums1 and nums2 cannot be both empty.
git clone -b beta https://github.com/flutter/flutter.git
¶first 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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120public static double middleNum(int[] a, int[] b) {
int alength = a.length;
int blength = b.length;
int am = alength / 2;
int bm = blength / 2;
double n = 0.0;
if(alength == 0){
if (blength % 2 == 0) {
System.out.println("偶数总数 :");
n = b[bm - 1] * 0.5 + b[bm] * 0.5;
} else {
System.out.println("奇数 : ");
n = b[bm];
}
return n;
}else if(blength == 0){
if (alength % 2 == 0) {
System.out.println("偶数总数 :");
n = a[am - 1] * 0.5 + a[am] * 0.5;
} else {
System.out.println("奇数 : ");
n = a[am];
}
return n;
}
int tn = a.length + b.length;
int mt = tn / 2;
System.out.println("a长度为:" + alength + ";中位数下标为:" + am);
System.out.println("b长度为:" + blength + ";中位数下标为:" + bm);
ArrayList<Integer> li = new ArrayList<>(20);
Integer[] c;
if (a[am] > b[bm]) {
for (int i = 0; i <= am; i++) {
li.add(a[i]);
}
System.out.println("");
for (int j = 0; j < blength; j++) {
li.add(b[j]);
}
System.out.println("");
// int[] c = new int[tn];
li.sort((o1, o2) -> {
if (o1 > o2) {
return 1;
} else if (o1 < o2) {
return -1;
} else {
return 0;
}
});
System.out.println(li.toString());
c = li.toArray(new Integer[0]);
Arrays.sort(c);
} else if (a[am] < b[bm]) {
for (int i = 0; i < alength; i++) {
li.add(a[i]);
}
System.out.println("");
for (int j = 0; j <= bm; j++) {
li.add(b[j]);
}
System.out.println("");
li.sort((o1, o2) -> {
if (o1 > o2) {
return 1;
} else if (o1 < o2) {
return -1;
} else {
return 0;
}
});
System.out.println(li.toString());
c = li.toArray(new Integer[0]);
Arrays.sort(c);
} else {
for (int i = 0; i <= am; i++) {
li.add(a[i]);
}
System.out.println("");
for (int j = 0; j <= bm; j++) {
li.add(b[j]);
}
System.out.println("");
li.sort((o1, o2) -> {
if (o1 > o2) {
return 1;
} else if (o1 < o2) {
return -1;
} else {
return 0;
}
});
System.out.println(li.toString());
c = li.toArray(new Integer[0]);
Arrays.sort(c);
}
System.out.println(mt);
if (tn % 2 == 0) {
System.out.println("偶数总数 :");
n = c[mt - 1] * 0.5 + c[mt] * 0.5;
} else {
System.out.println("奇数 : ");
n = c[mt];
}
return n;
}the answer was almost right but waste too much time ,the result run on leetCode is :
which means slower than 93% answer for this problem，what a terrible answer。It`s necessary to digout more potential for this code
¶Second 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
public double findMedianSortedArrays(int[] a, int[] b) {
int alength = a.length;
int blength = b.length;
int am = alength / 2;
int bm = blength / 2;
double n = 0.0;
if(alength == 0){
if (blength % 2 == 0) {
n = (b[bm - 1] + b[bm]) * 0.5;
} else {
n = b[bm];
}
return n;
}else if(blength == 0){
if (alength % 2 == 0) {
n = (a[am - 1] + a[am]) * 0.5;
} else {
n = a[am];
}
return n;
}
int tn = alength+blength;
int mt = tn / 2;
int[] c;
int k=0;
if (a[am] > b[bm]) {
c = new int[am + 1 + blength];
for (int i = 0; i <= am; i++) {
c[k] =a[i];
k++;
}
for (int j = 0; j < blength; j++) {
c[k] =b[j];
k++;
}
Arrays.sort(c);
} else if (a[am] < b[bm]) {
c = new int[bm + 1 + alength];
for (int i = 0; i < alength; i++) {
c[k] =a[i];
k++;
}
for (int j = 0; j <= bm; j++) {
c[k] =b[j];
k++;
}
Arrays.sort(c);
} else {
c = new int[am + 2 + bm];
for (int i = 0; i <= am; i++) {
c[k] =a[i];
k++;
}
for (int j = 0; j <= bm; j++) {
c[k] =b[j];
k++;
}
Arrays.sort(c);
}
if (tn % 2 == 0) {
n = (c[mt - 1]+ c[mt]) * 0.5;
} else {
n = c[mt];
}
return n;
}- delete the useless print info and unneeded ref of array length , but haven`t change the way to combine two array，maybe it is no need to combine the two array instead of some count of the midlle num index
- the resut shows :
- still slower than 60% answer ， try to repace combine array action with some traverse and index count
¶Thired Solution:
- //TODO