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)).
You may assume nums1 and nums2 cannot be both empty.
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
实现方式一:
public class Solution {
public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
int len1 = nums1.Length;
int len2 = nums2.Length;
int len = len1 + len2;
int[] nums = new int[len];
Array.Copy(nums1, nums, len1);
Array.Copy(nums2, 0, nums, len1, len2);
Array.Sort(nums);
if (len%2 == 0)
{
return (nums[len/2] + nums[len/2 - 1])*0.5;
}
return nums[len/2];
}
}
实现方式二:
由于题目要求时间复杂度为 O(log(m + n)),所以不能从两个有序数组的首尾挨个遍历来找到中位数(复杂度 O(m + n));而是要通过二分策略,通过每次比较,能够直接按比例的刷掉一组数字,最后找到中位数(复杂度 O(log(m + n)))。
中位数:用来将一个集合划分为两个长度相等的子集,其中一个子集中的元素总是大于另一个子集中的元素。
nums1: [a1,a2,a3,...am]
nums2: [b1,b2,b3,...bn]
[nums1[:i],nums2[:j] | nums1[i:], nums2[j:]]
nums1 取 i 个数的左半边
nums2 取 j = (m+n+1)/2 - i 的左半边
只要保证左右两边 个数 相同,中位数就在 |
这个边界旁边产生,从而可以利用二分法找到合适的 i。
public class Solution {
public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.Length;
int n = nums2.Length;
if (m > n)
return FindMedianSortedArrays(nums2, nums1);
int k = (m + n + 1)/2;
int left = 0;
int right = m;
while (left < right)
{
int i = (left + right)/2;
int j = k - i;
if (nums1[i] < nums2[j - 1])
left = i + 1;
else
right = i;
}
int m1 = left;
int m2 = k - left;
int c1 = Math.Max(m1 == 0 ? int.MinValue : nums1[m1 - 1],
m2 == 0 ? int.MinValue : nums2[m2 - 1]);
if ((m + n)%2 == 1)
return c1;
int c2 = Math.Min(m1 == m ? int.MaxValue : nums1[m1],
m2 == n ? int.MaxValue : nums2[m2]);
return (c1 + c2)*0.5;
}
}
实现方式一:
状态:通过
2085 / 2085 个通过测试用例
执行用时: 188 ms, 在所有 C# 提交中击败了 72.14% 的用户
实现方式二:
状态:通过
2085 / 2085 个通过测试用例
执行用时: 160 ms, 在所有 C# 提交中击败了 99.18% 的用户
相关图文:
经过8年多的发展,LSGO软件技术团队在「地理信息系统」、「数据统计分析」、「计算机视觉」等领域积累了丰富的研发经验,也建立了人才培养的完备体系,由于自己准备在「量化交易」领域精进技能,如果大家对这个领域感兴趣可以与我联系,加入我们的量化学习群一起学习探讨。
在这个领域我已做了以下积累:
策略部分:
数据部分:
自动化交易部分:
联系客服