题目: 寻找两个正序数组的中位数

来自智得网
跳转至： 导航、​ 搜索

方法一：归并法

  • 首先将两个正序数组合并为一个有序数组。
  • 然后根据数组的长度判断中位数的位置。
  • 如果数组长度为奇数，中位数即为合并后数组的中间元素。
  • 如果数组长度为偶数，中位数为合并后数组中中间两个元素的平均值。

归并法的时间复杂度是O（m+n），如果使用新的数组存储合并的数组，则空间复杂度也是O（m+n）。归并完成之后定位中位数的过程是O（1）的时间复杂度，所以该方法整体的时间复杂度是O（m+n）。 

#include <vector>
#include <algorithm>

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    vector<int> merged;
    merged.reserve(nums1.size() + nums2.size());
    
    // 合并两个有序数组
    merge(nums1.begin(), nums1.end(), nums2.begin(), nums2.end(), back_inserter(merged));
    
    int n = merged.size();
    if (n % 2 == 0) {
        return (merged[n/2 - 1] + merged[n/2]) / 2.0;
    } else {
        return merged[n/2];
    }
}

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int[] merged = new int[nums1.length + nums2.length];
    int i = 0, j = 0, k = 0;
    
    // 合并两个有序数组
    while (i < nums1.length && j < nums2.length) {
        if (nums1[i] < nums2[j]) {
            merged[k++] = nums1[i++];
        } else {
            merged[k++] = nums2[j++];
        }
    }
    
    while (i < nums1.length) {
        merged[k++] = nums1[i++];
    }
    
    while (j < nums2.length) {
        merged[k++] = nums2[j++];
    }
    
    int n = merged.length;
    if (n % 2 == 0) {
        return (merged[n/2 - 1] + merged[n/2]) / 2.0;
    } else {
        return merged[n/2];
    }
}

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    merged := make([]int, 0, len(nums1) + len(nums2))
    i, j := 0, 0
    
    // 合并两个有序数组
    for i < len(nums1) && j < len(nums2) {
        if nums1[i] < nums2[j] {
            merged = append(merged, nums1[i])
            i++
        } else {
            merged = append(merged, nums2[j])
            j++
        }
    }
    
    merged = append(merged, nums1[i:]...)
    merged = append(merged, nums2[j:]...)
    
    n := len(merged)
    if n % 2 == 0 {
        return float64(merged[n/2 - 1] + merged[n/2]) / 2.0
    } else {
        return float64(merged[n/2])
    }
}

def findMedianSortedArrays(nums1, nums2):
    merged = sorted(nums1 + nums2)
    n = len(merged)
    if n % 2 == 0:
        return (merged[n//2 - 1] + merged[n//2]) / 2.0
    else:
        return merged[n//2]

方法二：双指针

  • 使用两个指针分别指向两个数组的起始位置。
  • 通过比较指针所指元素的大小，将较小的元素放入新的数组中，并将对应指针向后移动一位。
  • 直到新的数组的长度达到中位数的位置。
  • 如果数组的总长度为奇数，中位数即为新数组的最后一个元素；
  • 如果数组的总长度为偶数，中位数为新数组的最后两个元素的平均值。
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int m = nums1.size();
    int n = nums2.size();
    int total = m + n;
    int left = (total + 1) / 2;
    int right = (total + 2) / 2;
    return (findKth(nums1, 0, m - 1, nums2, 0, n - 1, left) + findKth(nums1, 0, m - 1, nums2, 0, n - 1, right)) / 2.0;
}

int findKth(vector<int>& nums1, int start1, int end1, vector<int>& nums2, int start2, int end2, int k) {
    int len1 = end1 - start1 + 1;
    int len2 = end2 - start2 + 1;
    if (len1 > len2) {
        return findKth(nums2, start2, end2, nums1, start1, end1, k);
    }
    if (len1 == 0) {
        return nums2[start2 + k - 1];
    }
    if (k == 1) {
        return min(nums1[start1], nums2[start2]);
    }
    int i = start1 + min(len1, k / 2) - 1;
    int j = start2 + min(len2, k / 2) - 1;
    if (nums1[i] > nums2[j]) {
        return findKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
    } else {
        return findKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
    }
}

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int m = nums1.length;
    int n = nums2.length;
    int total = m + n;
    int left = (total + 1) / 2;
    int right = (total + 2) / 2;
    return (findKth(nums1, 0, m - 1, nums2, 0, n - 1, left) + findKth(nums1, 0, m - 1, nums2, 0, n - 1, right)) / 2.0;
}

public int findKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
    int len1 = end1 - start1 + 1;
    int len2 = end2 - start2 + 1;
    if (len1 > len2) {
        return findKth(nums2, start2, end2, nums1, start1, end1, k);
    }
    if (len1 == 0) {
        return nums2[start2 + k - 1];
    }
    if (k == 1) {
        return Math.min(nums1[start1], nums2[start2]);
    }
    int i = start1 + Math.min(len1, k / 2) - 1;
    int j = start2 + Math.min(len2, k / 2) - 1;
    if (nums1[i] > nums2[j]) {
        return findKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
    } else {
        return findKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
    }
}

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    m, n := len(nums1), len(nums2)
    total := m + n
    left, right := (total+1)/2, (total+2)/2
    return (float64(findKth(nums1, 0, m-1, nums2, 0, n-1, left)) + float64(findKth(nums1, 0, m-1, nums2, 0, n-1, right))) / 2.0
}

func findKth(nums1 []int, start1, end1 int, nums2 []int, start2, end2, k int) int {
    len1, len2 := end1-start1+1, end2-start2+1
    if len1 > len2 {
        return findKth(nums2, start2, end2, nums1, start1, end1, k)
    }
    if len1 == 0 {
        return nums2[start2+k-1]
    }
    if k == 1 {
        return min(nums1[start1], nums2[start2])
    }
    i := start1 + min(len1, k/2) - 1
    j := start2 + min(len2, k/2) - 1
    if nums1[i] > nums2[j] {
        return findKth(nums1, start1, end1, nums2, j+1, end2, k-(j-start2+1))
    } else {
        return findKth(nums1, i+1, end1, nums2, start2, end2, k-(i-start1+1))
    }
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

def findMedianSortedArrays(nums1, nums2):
    m, n = len(nums1), len(nums2)
    total = m + n
    left, right = (total + 1) // 2, (total + 2) // 2
    return (find_kth(nums1, 0, m - 1, nums2, 0, n - 1, left) + find_kth(nums1, 0, m - 1, nums2, 0, n - 1, right)) / 2.0

def find_kth(nums1, start1, end1, nums2, start2, end2, k):
    len1, len2 = end1 - start1 + 1, end2 - start2 + 1
    if len1 > len2:
        return find_kth(nums2, start2, end2, nums1, start1, end1, k)
    if len1 == 0:
        return nums2[start2 + k - 1]
    if k == 1:
        return min(nums1[start1], nums2[start2])
    i = start1 + min(len1, k // 2) - 1
    j = start2 + min(len2, k // 2) - 1
    if nums1[i] > nums2[j]:
        return find_kth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1))
    else:
        return find_kth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1))

方法三：二分法

  • 由于两个数组都是正序的，可以利用二分查找的思想来解决问题。
  • 首先确定要查找的中位数的位置，假设总元素个数为m+n，中位数的位置为k=(m+n+1)/2。
  • 然后对两个数组分别进行二分查找，找到第k个元素即可。
  • 如果m+n为奇数，中位数即为第k个元素；
  • 如果m+n为偶数，中位数为第k和k+1个元素的平均值。
#include <vector>
#include <algorithm>

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int m = nums1.size();
    int n = nums2.size();
    if (m > n) {
        swap(nums1, nums2);
        swap(m, n);
    }
    
    int left = 0;
    int right = m;
    int halfLen = (m + n + 1) / 2;
    
    while (left <= right) {
        int i = (left + right) / 2;
        int j = halfLen - i;
        
        if (i < m && nums2[j-1] > nums1[i]) {
            left = i + 1;
        } else if (i > 0 && nums1[i-1] > nums2[j]) {
            right = i - 1;
        } else {
            int maxLeft = 0;
            if (i == 0) {
                maxLeft = nums2[j-1];
            } else if (j == 0) {
                maxLeft = nums1[i-1];
            } else {
                maxLeft = max(nums1[i-1], nums2[j-1]);
            }
            
            if ((m + n) % 2 == 1) {
                return maxLeft;
            }
            
            int minRight = 0;
            if (i == m) {
                minRight = nums2[j];
            } else if (j == n) {
                minRight = nums1[i];
            } else {
                minRight = min(nums1[i], nums2[j]);
            }
            
            return (maxLeft + minRight) / 2.0;
        }
    }
    
    return 0.0; // 默认返回0.0，表示未找到中位数
}

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int m = nums1.length;
    int n = nums2.length;
    if (m > n) {
        int[] temp = nums1;
        nums1 = nums2;
        nums2 = temp;
        
        int tmp = m;
        m = n;
        n = tmp;
    }
    
    int left = 0;
    int right = m;
    int halfLen = (m + n + 1) / 2;
    
    while (left <= right) {
        int i = (left + right) / 2;
        int j = halfLen - i;
        
        if (i < m && nums2[j-1] > nums1[i]) {
            left = i + 1;
        } else if (i > 0 && nums1[i-1] > nums2[j]) {
            right = i - 1;
        } else {
            int maxLeft = 0;
            if (i == 0) {
                maxLeft = nums2[j-1];
            } else if (j == 0) {
                maxLeft = nums1[i-1];
            } else {
                maxLeft = Math.max(nums1[i-1], nums2[j-1]);
            }
            
            if ((m + n) % 2 == 1) {
                return maxLeft;
            }
            
            int minRight = 0;
            if (i == m) {
                minRight = nums2[j];
            } else if (j == n) {
                minRight = nums1[i];
            } else {
                minRight = Math.min(nums1[i], nums2[j]);
            }
            
            return (maxLeft + minRight) / 2.0;
        }
    }
    
    return 0.0; // 默认返回0.0，表示未找到中位数
}

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
    m := len(nums1)
    n := len(nums2)
    if m > n {
        nums1, nums2 = nums2, nums1
        m, n = n, m
    }
    
    left := 0
    right := m
    halfLen := (m + n + 1) / 2
    
    for left <= right {
        i := (left + right) / 2
        j := halfLen - i
        
        if i < m && nums2[j-1] > nums1[i] {
            left = i + 1
        } else if i > 0 && nums1[i-1] > nums2[j] {
            right = i - 1
        } else {
            maxLeft := 0
            if i == 0 {
                maxLeft = nums2[j-1]
            } else if j == 0 {
                maxLeft = nums1[i-1]
            } else {
                maxLeft = max(nums1[i-1], nums2[j-1])
            }
            
            if (m + n) % 2 == 1 {
                return float64(maxLeft)
            }
            
            minRight := 0
            if i == m {
                minRight = nums2[j]
            } else if j == n {
                minRight = nums1[i]
            } else {
                minRight = min(nums1[i], nums2[j])
            }
            
            return float64(maxLeft+minRight) / 2.0
        }
    }
    
    return 0.0 // 默认返回0.0，表示未找到中位数
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

def findMedianSortedArrays(nums1, nums2):
    m = len(nums1)
    n = len(nums2)
    if m > n:
        nums1, nums2 = nums2, nums1
        m, n = n, m
    
    left = 0
    right = m
    half_len = (m + n + 1) // 2
    
    while left <= right:
        i = (left + right) // 2
        j = half_len - i
        
        if i < m and nums2[j-1] > nums1[i]:
            left = i + 1
        elif i > 0 and nums1[i-1] > nums2[j]:
            right = i - 1
        else:
            if i == 0:
                max_left = nums2[j-1]
            elif j == 0:
                max_left = nums1[i-1]
            else:
                max_left = max(nums1[i-1], nums2[j-1])
            
            if (m + n) % 2 == 1:
                return float(max_left)
            
            if i == m:
                min_right = nums2[j]
            elif j == n:
                min_right = nums1[i]
            else:
                min_right = min(nums1[i], nums2[j])
            
            return float((max_left + min_right) / 2)
    
    return 0.0  # 默认返回0.0，表示未找到中位数
取自“https://www.aigetting.com/index.php?title=题目:寻找两个正序数组的中位数&oldid=2050”