Java [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)).

解题思路：

看到时间复杂度的时候就知道这种应该使用二分查找法了，否则如果实现log的时间复杂度？

思路已经有大神提供了，说的非常清楚，附上链接地址：http://my.oschina.net/jdflyfly/blog/283267

代码如下：

public class Solution {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {

		int total = nums1.length + nums2.length;

		if (total % 2 == 0)

			return (findKth(nums1, 0, nums1.length - 1, nums2, 0,

					nums2.length - 1, total / 2) + findKth(nums1, 0,

					nums1.length - 1, nums2, 0, nums2.length - 1, total / 2 + 1)) / 2;

		else

			return findKth(nums1, 0, nums1.length - 1, nums2, 0,

					nums2.length - 1, total / 2 + 1);

	}

	public double findKth(int[] a, int astart, int aend, int[] b,

			int bstart, int bend, int k) {

		if (aend - astart > bend - bstart)

			return findKth(b, bstart, bend, a, astart, aend, k);

		if (astart > aend)

			return b[k - 1];

		if (k == 1)

			return a[astart] > b[bstart] ? b[bstart] : a[astart];

		else {

			int la = Math.min(k / 2, aend - astart + 1);

			int lb = k - la;

			if (a[astart + la - 1] == b[bstart + lb - 1])

				return a[astart + la - 1];

			else if (a[astart + la - 1] < b[bstart + lb - 1])

				return findKth(a, astart + la, aend, b, bstart, bend, k - la);

			else

				return findKth(a, astart, aend, b, bstart + lb, bend, k - lb);

		}

	}

}

巴特西

Java [leetcode 4] Median of Two Sorted Arrays

最新文章

热门文章