本文主要是介绍LeetCode 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)).
题意：
就是给定两个数组，这两个数组已经排好序了，然后求这两个合并之后的数组的中位数。要求的时间复杂度为O(m+n)。我们可以发现，现在我们是不需要“排序”这么复杂的操作的，因为我们仅仅需要第k大的元素。我们可以用一个计数器，记录当前已经找到第m大的元素了。同时我们使用两个指针pA和pB，分别指向A和B数组的第一个元素。使用类似于merge sort的原理，如果数组A当前元素小，那么pA++，同时m++。如果数组B当前元素小，那么pB++，同时m++。最终当m等于k的时候，就得到了我们的答案——O(k)时间，O(1)空间。
public double findMedianSortedArrays(int[] nums1,int[] nums2){int l1 = nums1.length;int l2 = nums2.length;int median = 0;boolean odd = false;if((l1 + l2) % 2 != 0){odd = true;median = (l1 + l2) / 2;int i = 0;int j = 0;int k = 0;double medi = 0;while(i <= median){if(j < l1 && k < l2 && nums1[j] <= nums2[k]){if(i == median)medi = nums1[j];j++;}else if(j < l1 && k < l2 && nums1[j] > nums2[k]){if(i == median)medi = nums2[k];k++;}else if(j == l1 && k < l2){if(i == median)medi = nums2[k];k++;}else if(k == l2 && j < l1){if(i == median)medi = nums1[j];j++;}i++;}return medi;}else {median = (l1 + l2) / 2 - 1;int i = 0;int j = 0;int k = 0;int medi = 0;while(i <= median){if(j < l1 && k < l2 && nums1[j] <= nums2[k]){if(i == median)medi = nums1[j];j++;}else if(j < l1 && k < l2 && nums1[j] > nums2[k]){if(i == median)medi = nums2[k];k++;}else if(j == l1 && k < l2){if(i == median)medi = nums2[k];k++;}else if(k == l2 && j < l1){if(i == median)medi = nums1[j];j++;}i++;}double md = 0;if(j < l1 && k < l2 && nums1[j] <= nums2[k]){md = nums1[j];}else if(j < l1 && k < l2 && nums1[j] > nums2[k])md = nums2[k];else if(j == l1 && k <= l2)md = nums2[k];else if(j <= l1 && k == l2)md = nums1[j];return (medi + md) / 2;}}这篇关于LeetCode Median of Two Sorted Arrays的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
