题目:There are two sorted arrays A and B 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)).
看到题目,首先想到的是 把2个数组合并成一个,然后在去中间位置的数字。
后来发现时间复杂度为O(m+n);与题目不符合。
找了一些前辈的解题思路后自己模仿写了一个解法,并附上自己的理解。
代码:
public class Solution {
public double findMedianSortedArrays(int A[], int B[]) {
int m = A.length;
int n = B.length;
int total = m + n;
if(total%2==1)//如果是奇数,返回中间total/2 ,至于为何加1,我感觉是为了防止越界。
{
return findMed(A, m, B, n, total/2+1);
}
else //如果是偶数,返回中间2个的平均数
{
return (findMed(A, m, B, n, total/2)+findMed(A, m, B, n, total/2+1))/2;
}
}
public double findMed(int A[],int m,int B[],int n,int median)
{
if(m == 0)//如果是空,返回另一个的中位数
{
return B[median-1];
}
else if(n == 0)
{
return A[median-1];
}
else if(median == 1)//如果是第1个,则取这2个数的最小的为中位数
{
return Math.min(A[0],B[0]);
}
else if(m > n)//保证前面的是个数最小的数字 防止出现 A个数为2 B个数为8 median为8 median/2 大于2 数组会越界。
{
return findMed(B, n, A, m, median);
}
int am = Math.min(m, median/2);
int bm = median - am;
if(A[am-1] < B[bm-1])
{
return findMed(Arrays.copyOfRange(A, am, m), m-am, B, n, median-am);
}
else if(A[am-1]>B[bm-1])
{
return findMed(A, m, Arrays.copyOfRange(B, bm, n), n-bm, median-bm);
}
else return A[am-1];
}
}
二分查找,当计算m+n/2的时候,则可能出现越界的问题。
这个时候可以用n+ (m-n)/2,前提m>n来避免这种问题出现。
虽说是个不起眼的小技巧,不过以前还真没注意到。
分享到:
相关推荐
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)). Java AC版本
java java_leetcode题解之Median of Two Sorted Arrays.java
js js_leetcode题解之4-median-of-two-sorted-arrays.js
4. Median of Two Sorted Arrays 7. Reverse Integer 9. Palindrome Number 11. Container With Most Water 13. Roman to Integer 15. 3Sum 16. 3Sum Closest 17. Letter Combinations of a Phone Number 18. 4Sum ...
c语言入门 c语言_leetcode题解04-median-of-two-sorted-arrays.c
leetcode 无法登录两个有序数组的中位数 问题 有两个大小分别为 m 和 n 的排序数组 nums1 和 nums2。求两个排序数组的中位数。 整体运行时间复杂度应该是 O(log (m+n))。 您可以假设 nums1 和 nums2 不能都为空。 ...
java入门 java_leetcode题解之004_Median_of_Two_Sorted_Arrays
leetcode Python 001 leetcode的算法问题 这是我的解决方案,用 cpp 、 java 和 python 编写 #LeetCode 解决的问题: 001. Two Sum 002. Add Two Numbers 003. Longest Substring Without Repeating Characters4. ...
leetcode分类LeetCodeSourceCodes###LeetCode1TowSum如果数组是有序的,O(n)的时间复杂度就可以解决了,现在是无序的,一开始要排一下序###LeetCode2MedianofTwoSortedArrays让用logn的时间复杂度,用了两个二分,...
在LeetCode上,题目4(Median of Two Sorted Arrays)是一个经典的算法问题,旨在寻找两个已排序数组的中位数。中位数是将一组数值从小到大排列后处于中间位置的数,在奇数个数的情况下是中间的那个数,而在偶数个数...
lru缓存leetcode leetcode 1. Two Sum 2. Add Two Numbers 3. Longest Substring Without Repeating Characters 4. Median of Two Sorted Arrays 5. Longest Palindromic Substring 7. Reverse Integer 9. ...
leetcode Python 001 力码 ├── Algorithms │ ├── cpp │ │ ├── 001 - Two Sum.cpp │ │ ├── 002 - Add Two Numbers.cpp │ │ ├── 003 - Longest Substring Without Repeating ...
7 Median of Two Sorted Arrays 33 8 Kth Largest Element in an Array 35 9 Wildcard Matching 37 10 Regular Expression Matching in Java 39 11 Merge Intervals 43 12 Insert Interval 45 13 Two Sum 47 14 Two ...
#4:Median of Two Sorted Arrays 地图 #1:Two Sum #3:Longest Substring Without Repeating Characters #5:Longest Palindromic Substring 链表 #2:Add Two Numbers 分而治之 #53:Maximum Subarray 队列/集 #3:...
leetcode 2 Leetcode答案集 关于项目: 本项目包含本人LeetCode解题的答案,全部将由JavaScript语言进行解答。并会在每个题目的文件夹中添加相关的思路解析。 详情 # Title Solution Time Space Difficulty 1 Two ...
Median of Two Sorted Arrays 5 Longest Palindromic Substring 8 String to Integer 11 Container with Most Water 14 Longest Common Prefix 15 Three Sum 16 Three Sum Closest 20 Valid Parentheses 26 Remove ...
leetcode双人赛LeetCode 编号 题目 难度 题型 备注 Two Sum 简单 Add Two Numbers 中等 链结串列 重要 Longest Substring Without Repeating Characters 中等 字串 重要 Median of Two Sorted Arrays 困难 数学 ...
4.Median of Two Sorted Arrays 5.Longest Palindromic Substring (Manacher算法待完成) 6.ZigZag Conversion 7.Reverse Integer 8.String to Integer (atoi) 9.Palindrome Number 10.Regular Expression Matching ...
分割数组求最大差值leetcode LeetCode 学习之路 记录自己完成LeetCode的代码和结果。 序号 中文名称 英文名称 通过率 难度 1 Two Sum 47.0% 简单 2 Add Two Numbers 36.0% 中等 3 Longest Substring Without ...
* 两个排序数组的中位数(Median of Two Sorted Arrays):计算两个排序数组的中位数。 * 整数到罗马(Integer to Roman):将整数转换为罗马数字。 * 罗马到整数(Roman to Integer):将罗马数字转换为整数。 4...