2023-09-21 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's September LeetCoding Challenge with cpp.

September LeetCoding Challenge 21

Description

Median of Two Sorted Arrays

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

 

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

 

Constraints:

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -106 <= nums1[i], nums2[i] <= 106

Solution

auto speedup = [](){
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
  return 0;
}();
class Solution {
  int len1;
  int len2;
  int low;
  int high;
  int findCount(vector<int> &nums, int high, int num) {
    int low = 0;
    while(low < high) {
      int mid = (low + high + 1) >> 1;
      if(nums[mid] > num) {
        high = mid - 1;
      } else {
        low = mid;
      }
    }
    return low + (nums[low] <= num);
  }
  double findNthSortedArrays(vector<int>& nums1, vector<int>& nums2, int n) {
    if(nums1.empty()) return nums2[n - 1];
    if(nums2.empty()) return nums1[n - 1];
    int low = this->low;
    int high = this->high;
    while(low < high) {
      int mid = (low + high) >> 1;
      int count = findCount(nums1, len1 - 1, mid) + findCount(nums2, len2 - 1, mid);
      if(count < n) {
        low = mid + 1;
      } else {
        high = mid;
      }
    }
    return low;
  }
public:
  double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    low = min(nums1.size() ? nums1.front() : INT_MAX, nums2.size() ? nums2.front() : INT_MAX);
    high = max(nums1.size() ? nums1.back() : INT_MIN, nums2.size() ? nums2.back() : INT_MIN);
    len1 = nums1.size();
    len2 = nums2.size();
    pair<int, int> target = {(len1 + len2 + 1) / 2, (len1 + len2 + 2) / 2};
    return (findNthSortedArrays(nums1, nums2, target.first) + findNthSortedArrays(nums1, nums2, target.second)) / 2.0;
  }
};

// Accepted
// 2094/2094 cases passed (23 ms)
// Your runtime beats 76.84 % of cpp submissions
// Your memory usage beats 46.95 % of cpp submissions (89.7 MB)
Algorithm