8000 improved num 4 · SivaCse/leetcode-javascript@77db876 · GitHub
[go: up one dir, main page]
Skip to content

Commit 77db876

Browse files
chihungyu1116chihungyu1116
committed
improved num 4
1 parent a0d8aa1 commit 77db876

File tree

1 file changed

+73
-25
lines changed

1 file changed

+73
-25
lines changed

‎4. Median of Two Sorted Arrays.js

Lines changed: 73 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -1,46 +1,94 @@
1+
// /**
2+
// * @param {number[]} nums1
3+
// * @param {number[]} nums2
4+
// * @return {number}
5+
// */
6+
7+
// // http://blog.csdn.net/yutianzuijin/article/details/11499917
8+
// var findMedianSortedArrays = function(nums1, nums2) {
9+
// var m = nums1.length;
10+
// var n = nums2.length;
11+
// var total = m + n;
12+
13+
// if(total%2 === 1) {
14+
// return findKth(nums1, m, nums2, n, parseInt(total/2) + 1);
15+
// } else {
16+
// return (findKth(num 8000 s1, m, nums2, n, parseInt(total/2)) + findKth(nums1, m, nums2, n, parseInt(total/2) + 1))/2;
17+
// }
18+
// };
19+
20+
21+
// function findKth(a, m, b, n, k) {
22+
// // always assume that m is equal or smaller than n
23+
// if(m > n) {
24+
// return findKth(b, n, a, m, k);
25+
// }
26+
27+
// if(m === 0) {
28+
// return b[k-1];
29+
// }
30+
31+
// if(k === 1) {
32+
// return Math.min(a[0],b[0]);
33+
// }
34+
35+
// // divide k into two parts
36+
// var pa = Math.min(parseInt(k/2), m);
37+
// var pb = k - pa;
38+
39+
// if(a[pa - 1] < b[pb - 1]) {
40+
// return findKth(a.slice(pa), m - pa, b, n, k - pa);
41+
// } else if(a[pa - 1] > b[pb - 1]) {
42+
// return findKth(a, m, b.slice(pb), n - pb, k - pb);
43+
// } else {
44+
// return a[pa - 1];
45+
// }
46+
// }
47+
48+
149
/**
250
* @param {number[]} nums1
351
* @param {number[]} nums2
452
* @return {number}
553
*/
6-
7-
// http://blog.csdn.net/yutianzuijin/article/details/11499917
854
var findMedianSortedArrays = function(nums1, nums2) {
9-
var m = nums1.length;
10-
var n = nums2.length;
11-
var total = m + n;
55+
var total = nums1.length + nums2.length;
1256

13-
if(total%2 === 1) {
14-
return findKth(nums1, m, nums2, n, parseInt(total/2) + 1);
57+
if (total % 2 === 1) {
58+
return findKth(nums1, 0, nums2, 0, parseInt(total/2) + 1);
1559
} else {
16-
return (findKth(nums1, m, nums2, n, parseInt(total/2)) + findKth(nums1, m, nums2, n, parseInt(total/2) + 1))/2;
60+
return (
61+
findKth(nums1, 0, nums2, 0, parseInt(total/2))
62+
+ findKth(nums1, 0, nums2, 0, parseInt(total/2) + 1)
63+
)/2;
1764
}
1865
};
1966

20-
21-
function findKth(a, m, b, n, k) {
22-
// always assume that m is equal or smaller than n
23-
if(m > n) {
24-
return findKth(b, n, a, m, k);
67+
function findKth(nums1, start1, nums2, start2, kth) {
68+
var len1 = nums1.length - start1;
69+
var len2 = nums2.length - start2;
70+
71+
if (len1 > len2) {
72+
return findKth(nums2, start2, nums1, start1, kth);
2573
}
2674

27-
if(m === 0) {
28-
return b[k-1];
75+
if (len1 === 0) {
76+
return nums2[kth - 1];
2977
}
3078

31-
if(k === 1) {
32-
return Math.min(a[0],b[0]);
79+
if (kth === 1) {
80+
return Math.min(nums1[start1], nums2[start2]);
3381
}
3482

35-
// divide k into two parts
36-
var pa = Math.min(parseInt(k/2), m);
37-
var pb = k - pa;
83+
// divide kth into 2 parts
84+
var part1 = Math.min(parseInt(kth/2), len1);
85+
var part2 = kth - part1;
3886

39-
if(a[pa - 1] < b[pb - 1]) {
40-
return findKth(a.slice(pa), m - pa, b, n, k - pa);
41-
} else if(a[pa - 1] > b[pb - 1]) {
42-
return findKth(a, m, b.slice(pb), n - pb, k - pb);
87+
if (nums1[start1 + part1 - 1] < nums2[start2 + part2 - 1]) {
88+
return findKth(nums1, start1 + part1, nums2, start2, kth - part1);
89+
} else if (nums1[start1 + part1 - 1] > nums2[start2 + part2 - 1]) {
90+
return findKth(nums1, start1, nums2, start2 + part2, kth - part2);
4391
} else {
44-
return a[pa - 1];
92+
return nums1[start1 + part1 - 1];
4593
}
4694
}

0 commit comments

Comments
 (0)
0