首页 > 其他分享 >4. 寻找两个正序数组的中位数

4. 寻找两个正序数组的中位数

时间:2023-02-19 12:34:31浏览次数:60  
标签:正序 int 中位数 数组 nums1 nums2 size

给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

 

题解:采用了遍历的手法,刚好符合log(m + n)的时间复杂度,要注意两个数组总数和为奇数或者偶数的情况

#include "../include/leetcode.h"

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
          int left = (nums1.size() + nums2.size()) % 2;
          int medianPositioin = (nums1.size() + nums2.size()) / 2;
          //两个数组数量加起来是偶数的情况
          if (left == 0) {
               medianPositioin -= 1;
          }

          int index = 0;
          int i1, i2;
          double currentNum;
          for (i1 = i2 = 0; i1 < nums1.size() && i2 < nums2.size() && index <= medianPositioin;) {
               currentNum = nums1[i1] < nums2[i2] ? nums1[i1] : nums2[i2];
               if (currentNum == nums1[i1]) {
                    ++i1;
               }
               else {
                    ++i2;
               }
               index += 1;
          } 

          for (; i1 < nums1.size() && index <= medianPositioin; ++i1) {
               currentNum = nums1[i1];
               index += 1;
          } 

           for (; i2 < nums2.size() && index <= medianPositioin; ++i2) {
               currentNum = nums2[i2];
               index += 1;
          } 

          if(left == 1) {
               return currentNum;
          }
          else {
               double currentNextNum;
               if (i1 < nums1.size() && i2 < nums2.size()) {
                    currentNextNum = nums1[i1] < nums2[i2] ? nums1[i1] : nums2[i2];
               }
               else if (i1 < nums1.size()) {
                    currentNextNum = nums1[i1];
               }
               else if (i2 < nums2.size()){
                    currentNextNum = nums2[i2];
               }
               
               return (currentNextNum + currentNum) / 2;
          }       
    }
};

int main() {
     Solution s;
     vector<int> nums1{};
     vector<int> nums2{1};
     cout << s.findMedianSortedArrays(nums1, nums2) << endl;
     return 0;
}

  

标签:正序,int,中位数,数组,nums1,nums2,size
From: https://www.cnblogs.com/woodx/p/17134528.html

相关文章