leetcode 之Median of Two Sorted Arrays（五）

                  找两个排好序的数组的中间值，实际上可以扩展为寻找第k大的数组值。

                参考下面的思路，非常的清晰：

               

                  代码：

                            

double findMedianofTwoSortArrays(int A[], int B[], int m, int n){int total = m + n;//判断序列长度的奇偶，奇数只有一个中间值，偶数有两个中间值，取平均if (total & 0x1)return find_kth(A, m, B, n, total / 2 + 1);elsereturn (find_kth(A, m, B, n, total / 2) + find_kth(A, m, B, n, total / 2 + 1)) / 2;}int find_kth(int A[], int m, int B[], int n, int k){//设定m<=nif (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 ia = min(k / 2, m), ib = k - ia;if (A[ia - 1] < B[ib - 1])return find_kth(A + ia, m - ia, B, n, k - ia);else if (A[ia - 1]>B[ib - 1])return find_kth(A, m, B + ib, m - ib, k - ib);elsereturn A[ia - 1];} View Code

 

转载于:https://www.cnblogs.com/573177885qq/p/5492407.html

总结

以上是生活随笔为你收集整理的leetcode 之Median of Two Sorted Arrays（五）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。