现在的位置: 首页 > 编程技术 > 算法学习 > 正文

leetcode Median of Two Sorted Arrays 题解

2016年04月05日 算法学习 ⁄ 共 2443字 ⁄ 字号 评论 1 条 ⁄ 阅读 610 次

https://leetcode.com/problems/median-of-two-sorted-arrays/

1.暴力解法

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length;
		int m = nums2.length;
		if ((n + m) % 2 == 1) {
			return findKthNum(nums1, nums2, (n + m) / 2 + 1);
		} else {
			return new Double((findKthNum(nums1, nums2, (n + m) / 2) + findKthNum(nums1, nums2, (n + m) / 2 + 1)) / 2.0);
		}
    }
    
    public int findKthNum(int[] nums1, int[] nums2, int k) {
		if (nums1 == null || nums1.length == 0) {
			return nums2[k - 1];
		}
		if (nums2 == null || nums2.length == 0) {
			return nums1[k - 1];
		}
		int n = nums1.length;
		int m = nums2.length;
		if (n < k / 2) {
			if (nums1[n - 1] < nums2[k - n - 1]) { return findKthNum(null, nums2, k - n); } if (nums1[n - 1] == nums2[k - n - 1]) { return nums1[n - 1]; } if (nums1[n - 1] > nums2[k - n - 1]) {
				int[] temp = new int[m - (k - n)];
				for (int i = 0; i < temp.length; i++) {
					temp[i] = nums2[k - n + i];
				}
				return findKthNum(nums1, temp, k - (k - n));
			}
		}
		if (m < k / 2) { return findKthNum(nums2, nums1, k); } if (k == 1) { return Math.min(nums1[k / 2], nums2[k / 2]); } if (nums1[k / 2 - 1] > nums2[k / 2 - 1]) {
			int[] temp = new int[m - k / 2];
			for (int i = 0; i < temp.length; i++) {
				temp[i] = nums2[k / 2 + i];
			}
			return findKthNum(nums1, temp, k - k / 2);

		}
		if (nums1[k / 2 - 1] == nums2[k / 2 - 1]) {
			if (k % 2 == 1) {
				if (n < k / 2 + 1) {
					return nums2[k / 2];
				}
				if (m < k / 2 + 1) {
					return nums1[k / 2];
				}
				return Math.min(nums1[k / 2], nums2[k / 2]);
			}
			return nums1[k / 2 - 1];
		}
		if (nums1[k / 2 - 1] < nums2[k / 2 - 1]) {
			return findKthNum(nums2, nums1, k);
		}
		return 0;
	}
}

2.类似二分法查找第k个数

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length;
		int m = nums2.length;
		if ((n + m) % 2 == 1) {
			return findKthNum(nums1, nums2, (n + m) / 2 + 1);
		} else {
			return new Double((findKthNum(nums1, nums2, (n + m) / 2) + findKthNum(nums1, nums2, (n + m) / 2 + 1)) / 2.0);
		}
    }
    
    public int findKthNum(int[] nums1, int[] nums2, int k) {
		if (nums1 == null || nums1.length == 0) {
			return nums2[k - 1];
		}
		if (nums2 == null || nums2.length == 0) {
			return nums1[k - 1];
		}
		int n = nums1.length;
		int m = nums2.length;
		if (n < k / 2) {
			if (nums1[n - 1] < nums2[k - n - 1]) { return findKthNum(null, nums2, k - n); } if (nums1[n - 1] == nums2[k - n - 1]) { return nums1[n - 1]; } if (nums1[n - 1] > nums2[k - n - 1]) {
				int[] temp = new int[m - (k - n)];
				for (int i = 0; i < temp.length; i++) {
					temp[i] = nums2[k - n + i];
				}
				return findKthNum(nums1, temp, k - (k - n));
			}
		}
		if (m < k / 2) { return findKthNum(nums2, nums1, k); } if (k == 1) { return Math.min(nums1[k / 2], nums2[k / 2]); } if (nums1[k / 2 - 1] > nums2[k / 2 - 1]) {
			int[] temp = new int[m - k / 2];
			for (int i = 0; i < temp.length; i++) {
				temp[i] = nums2[k / 2 + i];
			}
			return findKthNum(nums1, temp, k - k / 2);

		}
		if (nums1[k / 2 - 1] == nums2[k / 2 - 1]) {
			if (k % 2 == 1) {
				if (n < k / 2 + 1) {
					return nums2[k / 2];
				}
				if (m < k / 2 + 1) {
					return nums1[k / 2];
				}
				return Math.min(nums1[k / 2], nums2[k / 2]);
			}
			return nums1[k / 2 - 1];
		}
		if (nums1[k / 2 - 1] < nums2[k / 2 - 1]) {
			return findKthNum(nums2, nums1, k);
		}
		return 0;
	}
}

目前有 1 条留言    访客:1 条, 博主:0 条

  1. zengda 2016年04月06日 下午4:14  Δ-9楼

    不错,不错,看看了!