menu 贺大礼(乱丶心)的博客 - 软件开发与技术分享
每日一题:4寻找两个有序数组的中位数
1768 浏览 | 2020-07-25 | 阅读时间: 约 1 分钟 | 分类: php,算法,算法与数据结构,C/C++ | 标签: 算法
请注意,本文编写于 1715 天前,最后修改于 1542 天前,其中某些信息可能已经过时。

给定两个大小为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。
请你找出这两个正序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:

  1. nums1 = [1, 3]
  2. nums2 = [2]
  3. 则中位数是 2.0

示例 2:

  1. nums1 = [1, 2]
  2. nums2 = [3, 4]
  3. 则中位数是 (2 + 3)/2 = 2.5

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/median-of-two-sorted-arrays

PHP解法

  1. class Solution {
  2. /**
  3. * @param Integer[] $nums1
  4. * @param Integer[] $nums2
  5. * @return Float
  6. */
  7. function findMedianSortedArrays($nums1, $nums2) {
  8. $a = array_merge($nums1, $nums2);
  9. $c = count($a);
  10. $k = (int)($c / 2);
  11. sort($a);
  12. if ($c % 2 === 0) {
  13. return ($a[$k] + $a[$k-1]) / 2;
  14. }
  15. return $a[$k];
  16. }
  17. }

作者:young-162
链接:https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/zhi-xing-yong-shi-32-ms-zai-suo-you-php-ti-jiao-2/

C语言解法

  1. #include <stdio.h>
  2. #include <vector>
  3. using namespace std;
  4. #define max(a,b) (((a) > (b)) ? (a) : (b))
  5. #define min(a,b) (((a) < (b)) ? (a) : (b))
  6. class Solution {
  7. public:
  8. double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
  9. int n = nums1.size();
  10. int m = nums2.size();
  11. if (n > m) //保证数组1一定最短
  12. {
  13. return findMedianSortedArrays(nums2, nums1);
  14. }
  15. // Ci 为第i个数组的割,比如C1为2时表示第1个数组只有2个元素。LMaxi为第i个数组割后的左元素。RMini为第i个数组割后的右元素。
  16. int LMax1, LMax2, RMin1, RMin2, c1, c2, lo = 0, hi = 2 * n; //我们目前是虚拟加了'#'所以数组1是2*n长度
  17. while (lo <= hi) //二分
  18. {
  19. c1 = (lo + hi) / 2; //c1是二分的结果
  20. c2 = m + n - c1;
  21. LMax1 = (c1 == 0) ? INT_MIN : nums1[(c1 - 1) / 2];
  22. RMin1 = (c1 == 2 * n) ? INT_MAX : nums1[c1 / 2];
  23. LMax2 = (c2 == 0) ? INT_MIN : nums2[(c2 - 1) / 2];
  24. RMin2 = (c2 == 2 * m) ? INT_MAX : nums2[c2 / 2];
  25. if (LMax1 > RMin2)
  26. hi = c1 - 1;
  27. else if (LMax2 > RMin1)
  28. lo = c1 + 1;
  29. else
  30. break;
  31. }
  32. return (max(LMax1, LMax2) + min(RMin1, RMin2)) / 2.0;
  33. }
  34. };
  35. int main(int argc, char *argv[])
  36. {
  37. vector<int> nums1 = { 2,3, 5 };
  38. vector<int> nums2 = { 1,4,7, 9 };
  39. Solution solution;
  40. double ret = solution.findMedianSortedArrays(nums1, nums2);
  41. return 0;
  42. }

作者:bian-bian-xiong
链接:https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/4-xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-shu/

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

发表评论

email
web

全部评论 (暂无评论)

info 还没有任何评论,你来说两句呐!

午后很容易犯困呢,今天的运动目标完成了吗?