题目
Median of Two Sorted Arrays Total Accepted: 4990 Total Submissions: 30805My Submissions
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)).
题意
有两个大小为m和n的已经排序的数组A,B。找到两个已排序的数组的中位数。总的运行时间复杂度应为O(log(M + N))。
思路一
这是一道非常经典的题。这题更通用的形式是,给定两个已经排序好的数组,找到两者所有元素中第 k 大的元素。O(m + n) 的解法比较直观,直接 merge 两个数组,然后求第 k 大的元素。不过我们仅仅需要第 k 大的元素,是不需要“排序”这么复杂的操作的。可以用一个计数器,记录当前已经找到第 m 大的元素了。同时我们使用两个指针 pA 和 pB,分别指向 A 和 B 数组的第一个元素,使用类似于 merge sort 的原理,如果数组 A 当前元素小,那么 pA++,同时 m++;如果数组 B 当前元素小,那么 pB++,同时 m++。最终当 m 等于 k 的时候,就得到了我们的答案,O(k)时间,O(1) 空间。但是,当 k 很接近 m + n 的时候,这个方法还是 O(m + n) 的。
代码一
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
double MedianSortArray(vector<int> num1,vector<int> num2){
int size1 = num1.size();
int size2 = num2.size();
if(size1 == 0 && size2 == 0){
return -1;
}
int mid = (size1 + size2 + 1) / 2 + 1;
int a,b,mid1 = 0,mid2 = 0;
int i = 0,j = 0,count = 0;
while(i < size1 || j < size2){
++count;
a = i < size1 ? num1[i] : INT_MAX;
b = j < size2 ? num2[j] : INT_MAX;
mid1 = mid2;
if(a < b){
++i;
mid2 = a;
}
else{
++j;
mid2 = b;
}
if(count == mid){
if((size1 + size2) & 1){
return mid1;
}
return (mid1 + mid2) / 2.0;
}
}
}
int main(){
vector<int> num1 = {1,4,8};
vector<int> num2 = {3,5};
cout<<MedianSortArray(num1,num2)<<endl;
return 0;
}
思路二
有没有更好的方案呢?我们可以考虑从 k 入手。如果我们每次都能够删除一个一定在第 k 大元素之前的元素,那么我们需要进行 k 次。但是如果每次我们都删除一半呢?由于 A 和 B 都是有序的,我们应该充分利用这里面的信息,类似于二分查找,也是充分利用了“有序”。假设 A 和 B 的元素个数都大于 k/2,我们将 A 的第 k/2 个元素(即 A[k/2-1])和 B 的第 k/2个元素(即 B[k/2-1])进行比较,有以下三种情况(为了简化这里先假设 k 为偶数,所得到的结论对于 k 是奇数也是成立的):
A[k/2-1] == B[k/2-1]
A[k/2-1] > B[k/2-1]
A[k/2-1] < B[k/2-1]
如果 A[k/2-1] < B[k/2-1],意味着 A[0] 到 A[k/2-1 的肯定在 A [ B 的 top k 元素的范围内,换句话说,A[k/2-1 不可能大于 A [ B 的第 k 大元素。留给读者证明。因此,我们可以放心的删除 A 数组的这 k/2 个元素。同理,当 A[k/2-1] > B[k/2-1] 时,可以删除 B 数组的 k/2 个元素。当 A[k/2-1] == B[k/2-1] 时,说明找到了第 k 大的元素,直接返回 A[k/2-1] 或 B[k/2-1]即可。因此,我们可以写一个递归函数。那么函数什么时候应该终止呢?
当 A 或 B 是空时,直接返回 B[k-1] 或 A[k-1];
当 k=1 是,返回 min(A[0], B[0]);
当 A[k/2-1] == B[k/2-1] 时,返回 A[k/2-1] 或 B[k/2-1]
代码
#include <iostream>
#include <stdio.h>
using namespace std;
class Solution {
public:
double findMedianSortedArrays(int A[], int m, int B[], int n) {
int total = (m + n);
if(total &0x1){
return find_kth(A,m,B,n,total/2+1);
}
else{
double a = find_kth(A,m,B,n,total/2);
double b = find_kth(A,m,B,n,total/2+1);
return (a + b) / 2;
}
}
private:
static double find_kth(int A[], int m, int B[], int n, int k) {
if (m > n) {
return find_kth(B, n, A, m, k);
}
if (m == 0) {
return B[k - 1];
}
if (k == 1) {
return min(A[0], B[0]);
}
int pa = min(k / 2, m);
int pb = k - pa;
if (A[pa - 1] < B[pb - 1]) {
return find_kth(A + pa, m - pa, B, n, k - pa);
}
else if (A[pa - 1] > B[pb - 1]) {
return find_kth(A, m, B + pb, n - pb, k - pb);
}
else {
return A[pa - 1];
}
}
};
int main() {
double result;
Solution solution;
int A[] = {};
int B[] = {1};
result = solution.findMedianSortedArrays(A,0,B,1);
printf("Result:%lf\n",result);
return 0;
}
<script type="text/javascript">
$(function () {
$('pre.prettyprint code').each(function () {
var lines = $(this).text().split('\n').length;
var $numbering = $('<ul/>').addClass('pre-numbering').hide();
$(this).addClass('has-numbering').parent().append($numbering);
for (i = 1; i <= lines; i++) {
$numbering.append($('<li/>').text(i));
};
$numbering.fadeIn(1700);
});
});
</script>
分享到:
相关推荐
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版本
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 ...
Median of Two Sorted Arrays 注意:后两题是与快速排序非常相似的快速选择(Quick Select)算法,面试中很常考 链表类(Linked List): 基础知识:链表如何实现,如何遍历链表。链表可以保证头部尾部插入删除操作...
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 leetcode的算法问题 这是我的解决方案,用 cpp 、 java 和 python 编写 #LeetCode 解决的问题: 001. Two Sum 002. Add Two Numbers 003. Longest Substring Without Repeating Characters4. ...
leetcode 无法登录两个有序数组的中位数 问题 有两个大小分别为 m 和 n 的排序数组 nums1 和 nums2。求两个排序数组的中位数。 整体运行时间复杂度应该是 O(log (m+n))。 您可以假设 nums1 和 nums2 不能都为空。 ...
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 ...
4.Median of Two Sorted Arrays 7.Reverse Integer 8.String to Integer (atoi) 9.Palindrome Number 11.Container With Most Water 14.Longest Common Prefix 15.3Sum 16.3Sum Closest 19.Remove Nth Node From End...
4.Median of Two Sorted Arrays 5.Longest Palindromic Substring 6.ZigZag Conversion 7.Reverse Integer 8.String To Integer 9.Palindrome Number 10.String To Integer 11.Container With Most Water 12.Integer...
Median of Two Sorted Arrays 求两有序数列的中位数,可泛化为求两有序数列的第k位数,二分法 5. Longest Palindromic Substring 最长回文子串,补符号,记忆 6. ZigZag Conversion 观察规律 7. Reverse Integer ...
leetcode 跳跃 LeetCode Solved by Python easy/middle/hard:15/36/5 1. Two Sum 两数之和 2. Add Two Numbers 两数相加 3. Longest Substring Without Repeating Characters 无重复字符的最长子串 4. Median of ...
leetcode 2 sum c Leetcode 记录我的Leetcode之旅 题号 难度 知识点 完成情况 1. Two Sum Easy 搜索 :check_mark_button: 2. Add Two Numbers Medium 链表 :check_mark_button: 3. Longest Substring Without ...
Arrays.cpp │ │ └── 005 - Longest Palindromic Substring.cpp │ └── python │ ├── 001 - Two Sum.py │ ├── 002 - Add Two Numbers.py │ ├── 003 - Longest Substring Without ...
leetcode 知乎 此项目介绍 此项目旨在是为leetcode里面的习题提供解析(数据结构相关知识),锻炼了自己,同时也给别人带来了方便。 网站习题链接: ** 作者知乎链接**: 关于习题 所有习题和解析都写在一个文件里,...
leetcode数组下标大于间距 LeetCode_Solutions :party_popper:My LeetCode solutions 0001. Two Sum 0002. Add Two Numbers 0003. Longest Substring Without Repeating Characters 解题思路 使用 st[i] 保存以i结尾...
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 ...
leetcode 不会 此项目用于记录本人leetcode刷题的代码 2. Median of Two Sorted Arrays Star 暴力解法, apparently won't be accepted. 二分查找 left | right A[0]...A[i] | A[i+1]...A[m-1] B[0]...B[j] | B[j+1]...
蓄水池算法 leetcode Leetcode Solutions Continue updating... lt: leetcode jz: 剑指Offer Sort & Search # Name Difficulty ...Two ...Two ...lt.4 Median of Two Sorted Arrays hard [python] lt.5 Longest Pa
leetcode添加元素使和等于 LeetCodeNotes Array: 4. Median of Two Sorted Arrays 思路: 基于二分查找的思想 88. Merge Sorted Array 描述:合并两个有序数组,将B合并入A,A长度刚好为A.length + B.length nums1 =...
231 | [Power of Two](https://leetcode.com/problems/power-of-two/) | [C++](./C++/power-of-two.cpp) [Python](./Python/power-of-two.py) | _O(1)_ | _O(1)_ | Easy | LintCode | 260 | [Single Number III]...