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(nums1, 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
854var 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- // dividek intotwo parts
36- var pa = Math . min ( parseInt ( k / 2 ) , m ) ;
37- var pb = k - pa ;
83+ // dividekth into2 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}