博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
LeetCode4. Median of Two Sorted Arrays
阅读量:5861 次
发布时间:2019-06-19

本文共 3175 字,大约阅读时间需要 10 分钟。

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

除了要想到通过寻找第k大的数来优化算法外,此题还有非常变态的边界处理

class Solution {public:	int fuck(int sx,int x,vector
& a,int sy,int y,vector
& b,int k) { if(x-sx>y-sy) return fuck(sy,y,b,sx,x,a,k); if(x==sx) return b[sy+k-1]; if(k==1) { if(a[sx]
& nums1, vector
& nums2) { int len1=nums1.size(); int len2=nums2.size(); if((len1+len2)&1) return fuck(0,len1,nums1,0,len2,nums2,(len1+len2)/2+1); else { return (fuck(0,len1,nums1,0,len2,nums2,(len1+len2)/2)+ fuck(0,len1,nums1,0,len2,nums2,(len1+len2)/2+1))/2.0; } }};

 嘛,找第k大的做法是这样地

Assume that the number of elements in A and B are both larger than k/2, and if we compare the k/2-th smallest element in A(i.e. A[k/2-1]) and the k-th smallest element in B(i.e. B[k/2 - 1]), there are three results:

(Becasue k can be odd or even number, so we assume k is even number here for simplicy. The following is also true when k is an odd number.)
A[k/2-1] = B[k/2-1]
A[k/2-1] > B[k/2-1]
A[k/2-1] < B[k/2-1]
if A[k/2-1] < B[k/2-1], that means all the elements from A[0] to A[k/2-1](i.e. the k/2 smallest elements in A) are in the range of k smallest elements in the union of A and B. Or, in the other word, A[k/2 - 1] can never be larger than the k-th smalleset element in the union of A and B.
Why?
We can use a proof by contradiction. Since A[k/2 - 1] is larger than the k-th smallest element in the union of A and B, then we assume it is the (k+1)-th smallest one. Since it is smaller than B[k/2 - 1], then B[k/2 - 1] should be at least the (k+2)-th smallest one. So there are at most (k/2-1) elements smaller than A[k/2-1] in A, and at most (k/2 - 1) elements smaller than A[k/2-1] in B.So the total number is k/2+k/2-2, which, no matter when k is odd or even, is surly smaller than k(since A[k/2-1] is the (k+1)-th smallest element). So A[k/2-1] can never larger than the k-th smallest element in the union of A and B if A[k/2-1]<B[k/2-1];
Since there is such an important conclusion, we can safely drop the first k/2 element in A, which are definitaly smaller than k-th element in the union of A and B. This is also true for the A[k/2-1] > B[k/2-1] condition, which we should drop the elements in B.
When A[k/2-1] = B[k/2-1], then we have found the k-th smallest element, that is the equal element, we can call it m. There are each (k/2-1) numbers smaller than m in A and B, so m must be the k-th smallest number. So we can call a function recursively, when A[k/2-1] < B[k/2-1], we drop the elements in A, else we drop the elements in B.
We should also consider the edge case, that is, when should we stop?
1. When A or B is empty, we return B[k-1]( or A[k-1]), respectively;
2. When k is 1(when A and B are both not empty), we return the smaller one of A[0] and B[0]
3. When A[k/2-1] = B[k/2-1], we should return one of them
In the code, we check if m is larger than n to garentee that the we always know the smaller array, for coding simplicy.

之后调试了很久的边界。。总结额外要主意几种情况

1.当k/2大于当前A数组长度时

2.当k/2大于当前A数组长度时

3.当k/2大于当前A数组长度时

嘛,写了几遍wa都怎么想也想不到,试很久才试出来的。其实如果要独自构思整个思路,还要考虑到A is empty和k==1这两种情况,都挺难想的

转载于:https://www.cnblogs.com/bitch1319453/p/6595190.html

你可能感兴趣的文章
http://q.cnblogs.com/q/39321/
查看>>
【BZOJ】1635: [Usaco2007 Jan]Tallest Cow 最高的牛
查看>>
牛客练习赛10
查看>>
数据库内连接、外连接、左连接、右连接、全连接
查看>>
Leetcode House Robber
查看>>
实验五
查看>>
keypress 、keydown、keyup后触发回车
查看>>
非节点主机通过内网远程管理docker swarm集群
查看>>
js判断PC端还是移动端
查看>>
远程协助
查看>>
BETA 版冲刺前准备
查看>>
欧拉函数
查看>>
Ubuntu Kylin 14.04下配置JDK1.8
查看>>
Unable to locate package错误解决办法
查看>>
Linux常用命令总结
查看>>
2013.5.29
查看>>
Fiddler实现手机抓包——小白入门(转载csdn)
查看>>
Scrum实施日记 - 一切从零开始
查看>>
Windows中安装Emacs
查看>>
vim tab四个空格修改
查看>>