pizda

mail@pastecode.io avatar
unknown
rust
5 months ago
3.7 kB
2
Indexable
Never
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        merged = []
        i, j = 0, 0
        
        while i < len(nums1) and j < len(nums2):
            if nums1[i] < nums2[j]:
                merged.append(nums1[i])
                i += 1
            else:
                merged.append(nums2[j])
                j += 1
                
        while i < len(nums1):
            merged.append(nums1[i])
            i += 1
            
        while j < len(nums2):
            merged.append(nums2[j])
            j += 1
        
        mid = len(merged) // 2
        if len(merged) % 2 == 0:
            return (merged[mid-1] + merged[mid]) / 2
        else:
            return merged[mid]
Binary Search with Partitioning
The problem can be elegantly solved using binary search by partitioning the two arrays such that elements on the left are smaller or equal to elements on the right.

Key Data Structures:
partitionX and partitionY: To store the partition indices for nums1 and nums2 respectively.
maxX, minX, maxY, minY: To store the values around the partition in both arrays.
Enhanced Breakdown:
Initialize and Swap Arrays if Needed:

Swap nums1 and nums2 if nums1 is larger. This ensures we always binary search the smaller array, optimizing the time complexity.
Binary Search Setup:

Initialize low to 0 and high to the size of the smaller array.
Start Binary Search Loop:

The loop continues until low is not greater than high.
Calculate partitionX and partitionY based on low and high.
Calculate Partition Values:

Compute maxX, minX, maxY, minY based on the partitions.
Check for Correct Partition:

If maxX <= minY and maxY <= minX, we have found the correct partition.
Calculate and return the median based on the values around the partition.
Adjust Binary Search Bounds:

If maxX > minY, adjust high to partitionX - 1.
Otherwise, adjust low to partitionX + 1.
Complexity Analysis:
Time Complexity:

The algorithm performs a binary search on the smaller array, leading to a time complexity of O(log⁡(min⁡(m,n)))O(\log(\min(m, n)))O(log(min(m,n))).
Space Complexity:

The algorithm uses only a constant amount of extra space, thus having a space complexity of O(1)O(1)O(1).
Code Binary Search
impl Solution {
    pub fn find_median_sorted_arrays(nums1: Vec<i32>, nums2: Vec<i32>) -> f64 {
        let (mut nums1, mut nums2) = if nums1.len() > nums2.len() {
            (nums2, nums1)
        } else {
            (nums1, nums2)
        };
        
        let (m, n) = (nums1.len(), nums2.len());
        let (mut low, mut high) = (0, m);
        
        while low <= high {
            let partition_x = (low + high) / 2;
            let partition_y = (m + n + 1) / 2 - partition_x;
            
            let max_x = if partition_x == 0 { i32::MIN } else { nums1[partition_x - 1] };
            let min_x = if partition_x == m { i32::MAX } else { nums1[partition_x] };
            
            let max_y = if partition_y == 0 { i32::MIN } else { nums2[partition_y - 1] };
            let min_y = if partition_y == n { i32::MAX } else { nums2[partition_y] };
            
            if max_x <= min_y && max_y <= min_x {
                if (m + n) % 2 == 0 {
                    return (max_x.max(max_y) + min_x.min(min_y)) as f64 / 2.0;
                } else {
                    return max_x.max(max_y) as f64;
                }
            } else if max_x > min_y {
                high = partition_x - 1;
            } else {
                low = partition_x + 1;
            }
        }
        
        0.0
    }
}