LeetCode //C - 4. Median of Two Sorted Arrays

这篇具有很好参考价值的文章主要介绍了LeetCode //C - 4. Median of Two Sorted Arrays。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

4. 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
  • − 1 0 6 < = n u m s 1 [ i ] , n u m s 2 [ i ] < = 1 0 6 -10^6 <= nums1[i], nums2[i] <= 10^6 106<=nums1[i],nums2[i]<=106

From: LeetCode
Link: 4. Median of Two Sorted Arrays


Solution:

Ideas:

In this code, findMedianSortedArrays function takes two sorted arrays nums1 and nums2, along with their sizes nums1Size and nums2Size, and returns the median of the combined array.

The algorithm first ensures that nums1 is the smaller array to optimize the binary search. It then performs a binary search on the smaller array, trying to find a partition such that the elements on the left side of the partition from both arrays are smaller than the elements on the right side of the partition from both arrays. Once the correct partition is found, it calculates the median based on the combined size of both arrays being even or odd.文章来源地址https://www.toymoban.com/news/detail-738461.html

Code:
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    // Ensure nums1 is the smaller array
    if (nums1Size > nums2Size) {
        return findMedianSortedArrays(nums2, nums2Size, nums1, nums1Size);
    }
    
    int x = nums1Size;
    int y = nums2Size;

    int low = 0;
    int high = x;
    
    while (low <= high) {
        int partitionX = (low + high) / 2;
        int partitionY = (x + y + 1) / 2 - partitionX;
        
        int maxX = (partitionX == 0) ? INT_MIN : nums1[partitionX - 1];
        int maxY = (partitionY == 0) ? INT_MIN : nums2[partitionY - 1];
        
        int minX = (partitionX == x) ? INT_MAX : nums1[partitionX];
        int minY = (partitionY == y) ? INT_MAX : nums2[partitionY];
        
        if (maxX <= minY && maxY <= minX) {
            // We have partitioned array at correct place
            if ((x + y) % 2 == 0) {
                return ((double) fmax(maxX, maxY) + fmin(minX, minY)) / 2;
            } else {
                return (double) fmax(maxX, maxY);
            }
        } else if (maxX > minY) {
            high = partitionX - 1;
        } else {
            low = partitionX + 1;
        }
    }
    
    // If input arrays are not sorted or not valid
    return -1.0;
}

到了这里,关于LeetCode //C - 4. Median of Two Sorted Arrays的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode //2723. Add Two Promises (Day 30 of LC JavaScript Challenage)

    Given two promises promise1 and promise2 , return a new promise. promise1 and promise2 will both resolve with a number. The returned promise should resolve with the sum of the two numbers.   Example 1: Input: promise1 = new Promise(resolve = setTimeout(() = resolve(2), 20)), promise2 = new Promise(resolve = setTimeout(() = resolve(5), 60)) Output: 7 Explana

    2024年02月11日
    浏览(39)
  • LeetCode --- 1880. Check if Word Equals Summation of Two Words 解题报告

    The  letter value  of a letter is its position in the alphabet  starting from 0  (i.e.  \\\'a\\\' - 0 ,  \\\'b\\\' - 1 ,  \\\'c\\\' - 2 , etc.). The  numerical value  of some string of lowercase English letters  s  is the  concatenation  of the  letter values  of each letter in  s , which is then  converted  into an integer. For example, if  s = \\\"acb\\\" , we

    2024年02月13日
    浏览(44)
  • LeetCode //88. Merge Sorted Array

    You are given two integer arrays nums1 and nums2 , sorted in non-decreasing order, and two integers m and n , representing the number of elements in nums1 and nums2 respectively. Merge nums1 and nums2 into a single array sorted in non-decreasing order. The final sorted array should not be returned by the function, but instead be stored inside the array nums1

    2024年02月12日
    浏览(45)
  • LeetCode 1. Two Sum 两数之和

    题目描述 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2

    2023年04月25日
    浏览(43)
  • LeetCode83. Remove Duplicates from Sorted List

    Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well. Example 1: Input: head = [1,1,2] Output: [1,2] Example 2: Input: head = [1,1,2,3,3] Output: [1,2,3] Constraints: The number of nodes in the list is in the range [0, 300]. -100 = Node.val = 100 The list is guaranteed t

    2024年01月18日
    浏览(48)
  • LeetCode //80. Remove Duplicates from Sorted Array II

    Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same. Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums

    2024年02月13日
    浏览(50)
  • Leetcode 82. Remove Duplicates from Sorted List II

    Remove Duplicates from Sorted List II Medium Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well. Example 1: Input: head = [1,2,3,3,4,4,5] Output: [1,2,5] Example 2: Input: head = [1,1,1,2,3] Output: [2,3] Constraints: The number of n

    2024年02月10日
    浏览(46)
  • leetcode 445. Add Two Numbers II(两数相加)

    用链表代表2个数字,这2个数字相加的和用链表返回。 最高位在链表的head. 思路: 1.链表逆序 数字相加是从低位到高位的,然而链表中的数字是从高位指向低位。 所以涉及到链表的逆序。 逆序之后只需从head到tail把两个链表的数字相加,再用一个int表示进位。 链表的逆序

    2024年02月16日
    浏览(46)
  • LeetCode //C - 153. Find Minimum in Rotated Sorted Array

    Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become: [4,5,6,7,0,1,2] if it was rotated 4 times. [0,1,2,4,5,6,7] if it was rotated 7 times. Notice that rotating an array [a[0], a[1], a[2], …, a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], …, a[n

    2024年02月06日
    浏览(36)
  • Algorithms practice:leetcode 33. Search in Rotated Sorted Array

    Algorithms practice:leetcode33 Search in Rotated Sorted Array There is an integer array ,nums , sorted in ascending order (with distinct values). Prior to being passed to your function, nums is possibly rotated,at an unknown pivot index k (1 = k nums.length) such that the resulting array is [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums

    2024年01月21日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包