Skip to content

Latest commit

 

History

History
141 lines (127 loc) · 28.6 KB

4 Median of two arrays 二分法 查找.md

File metadata and controls

141 lines (127 loc) · 28.6 KB

There are two sorted arrays nums1 and nums2 of size m and n
respectively.

Find the median of the two sorted arrays. The overall run time
complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

题目

初始解法

import numpy as np
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        nums = []
        i = j =0
        while nums1 and nums2:
            if nums1[0] <= nums2[0]:
                nums.append(nums1.pop(0))
            elif nums2[0] <= nums1[0]:
                nums.append(nums2.pop(0))
        if nums1:
            nums+=nums1
        else :
            nums+=nums2
        return np.median(nums)

是merge的思想 但是时间复杂度是O(m+n) 并不满足提意
是一种超级慢的做法

官方解法

def median(A, B):
    m, n = len(A), len(B)
    if m > n:
        A, B, m, n = B, A, n, m
    if n == 0:
        raise ValueError

imin<span class="token punctuation">,</span> imax<span class="token punctuation">,</span> half_len <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">,</span> m<span class="token punctuation">,</span> <span class="token punctuation">(</span>m <span class="token operator">+</span> n <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">/</span> <span class="token number">2</span>
<span class="token keyword">while</span> imin <span class="token operator">&lt;=</span> imax<span class="token punctuation">:</span>
    i <span class="token operator">=</span> <span class="token punctuation">(</span>imin <span class="token operator">+</span> imax<span class="token punctuation">)</span> <span class="token operator">/</span> <span class="token number">2</span>
    j <span class="token operator">=</span> half_len <span class="token operator">-</span> i
    <span class="token keyword">if</span> i <span class="token operator">&lt;</span> m <span class="token operator">and</span> B<span class="token punctuation">[</span>j<span class="token number">-1</span><span class="token punctuation">]</span> <span class="token operator">&gt;</span> A<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">:</span>
        <span class="token comment"># i is too small, must increase it</span>
        imin <span class="token operator">=</span> i <span class="token operator">+</span> <span class="token number">1</span>
    <span class="token keyword">elif</span> i <span class="token operator">&gt;</span> <span class="token number">0</span> <span class="token operator">and</span> A<span class="token punctuation">[</span>i<span class="token number">-1</span><span class="token punctuation">]</span> <span class="token operator">&gt;</span> B<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">:</span>
        <span class="token comment"># i is too big, must decrease it</span>
        imax <span class="token operator">=</span> i <span class="token operator">-</span> <span class="token number">1</span>
    <span class="token keyword">else</span><span class="token punctuation">:</span>
        <span class="token comment"># i is perfect</span>

        <span class="token keyword">if</span> i <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">:</span> max_of_left <span class="token operator">=</span> B<span class="token punctuation">[</span>j<span class="token number">-1</span><span class="token punctuation">]</span>
        <span class="token keyword">elif</span> j <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">:</span> max_of_left <span class="token operator">=</span> A<span class="token punctuation">[</span>i<span class="token number">-1</span><span class="token punctuation">]</span>
        <span class="token keyword">else</span><span class="token punctuation">:</span> max_of_left <span class="token operator">=</span> <span class="token builtin">max</span><span class="token punctuation">(</span>A<span class="token punctuation">[</span>i<span class="token number">-1</span><span class="token punctuation">]</span><span class="token punctuation">,</span> B<span class="token punctuation">[</span>j<span class="token number">-1</span><span class="token punctuation">]</span><span class="token punctuation">)</span>

        <span class="token keyword">if</span> <span class="token punctuation">(</span>m <span class="token operator">+</span> n<span class="token punctuation">)</span> <span class="token operator">%</span> <span class="token number">2</span> <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">:</span>
            <span class="token keyword">return</span> max_of_left

        <span class="token keyword">if</span> i <span class="token operator">==</span> m<span class="token punctuation">:</span> min_of_right <span class="token operator">=</span> B<span class="token punctuation">[</span>j<span class="token punctuation">]</span>
        <span class="token keyword">elif</span> j <span class="token operator">==</span> n<span class="token punctuation">:</span> min_of_right <span class="token operator">=</span> A<span class="token punctuation">[</span>i<span class="token punctuation">]</span>
        <span class="token keyword">else</span><span class="token punctuation">:</span> min_of_right <span class="token operator">=</span> <span class="token builtin">min</span><span class="token punctuation">(</span>A<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">,</span> B<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span>

        <span class="token keyword">return</span> <span class="token punctuation">(</span>max_of_left <span class="token operator">+</span> min_of_right<span class="token punctuation">)</span> <span class="token operator">/</span> <span class="token number">2.0</span>

分析过程较长 在这里不赘述 只说一下思路

  1. 先是分析中位数应该满足的参数（i是数组a的划分点,j是数组b的划分点）条件 算法目的就在寻找这个i
  2. A[i-1]<B[j] && B[j-1]<A[i] （保证左边的任意元素小于右边的任意元素）和 i+j = m+n-i-j（左右两边元素个数一样）
  3. 根据条件不等式的左右大小确定参数的变化方向 改变i的上下界 一次缩小一半
  4. 根据数组的索引考虑边界情况

问题一般化

问题可以一般化为

求两个有序数组的第k个数

一般来说求第k个数的方法

  1. 分别求出第一个和第二个数组的第 k / 2个数 a 和 b
  2. 然后比较 a 和 b，当a < b ，说明第 k 个数位于 a数组的第 k / 2个数后半段，或者b数组的 第 k / 2 个数前半段
  3. 步长缩小一半，继续递归处理。

速度比较慢 但是是一种具有普适性的做法

非递归做法

import numpy as np
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        m = len(nums1)
        n = len(nums2)
        if (m+n)%2 :
            return self.find(nums1,0,nums2,0,(m+n)//2+1)
        else:
            return (self.find(nums1,0,nums2,0,(m+n)//2) + self.find(nums1,0,nums2,0,(m+n)//2+1))/2

<span class="token keyword">def</span> <span class="token function">find</span><span class="token punctuation">(</span>self<span class="token punctuation">,</span> a<span class="token punctuation">,</span> a_begin<span class="token punctuation">,</span>b<span class="token punctuation">,</span>b_begin<span class="token punctuation">,</span>k<span class="token punctuation">)</span><span class="token punctuation">:</span>
    <span class="token keyword">while</span> a_begin<span class="token operator">&lt;</span><span class="token builtin">len</span><span class="token punctuation">(</span>a<span class="token punctuation">)</span> <span class="token operator">and</span> b_begin <span class="token operator">&lt;</span> <span class="token builtin">len</span><span class="token punctuation">(</span>b<span class="token punctuation">)</span><span class="token punctuation">:</span>
        <span class="token keyword">if</span> k<span class="token operator">==</span><span class="token number">1</span> <span class="token punctuation">:</span>
            <span class="token keyword">return</span> <span class="token builtin">min</span><span class="token punctuation">(</span>a<span class="token punctuation">[</span>a_begin<span class="token punctuation">]</span><span class="token punctuation">,</span>b<span class="token punctuation">[</span>b_begin<span class="token punctuation">]</span><span class="token punctuation">)</span>
        a_k <span class="token operator">=</span> a<span class="token punctuation">[</span>a_begin <span class="token operator">+</span> k<span class="token operator">//</span><span class="token number">2</span> <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token keyword">if</span> a_begin <span class="token operator">+</span> k<span class="token operator">//</span><span class="token number">2</span> <span class="token operator">-</span> <span class="token number">1</span> <span class="token operator">&lt;</span> <span class="token builtin">len</span><span class="token punctuation">(</span>a<span class="token punctuation">)</span> <span class="token keyword">else</span> <span class="token number">100000</span>
        b_k <span class="token operator">=</span> b<span class="token punctuation">[</span>b_begin <span class="token operator">+</span> k<span class="token operator">//</span><span class="token number">2</span> <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token keyword">if</span> b_begin <span class="token operator">+</span> k<span class="token operator">//</span><span class="token number">2</span> <span class="token operator">-</span> <span class="token number">1</span> <span class="token operator">&lt;</span> <span class="token builtin">len</span><span class="token punctuation">(</span>b<span class="token punctuation">)</span> <span class="token keyword">else</span> <span class="token number">100000</span> 
        
        <span class="token keyword">if</span> a_k <span class="token operator">&lt;</span> b_k<span class="token punctuation">:</span>
            a_begin <span class="token operator">=</span> a_begin <span class="token operator">+</span> k<span class="token operator">//</span><span class="token number">2</span>
        <span class="token keyword">else</span><span class="token punctuation">:</span>
            b_begin <span class="token operator">=</span> b_begin <span class="token operator">+</span> k<span class="token operator">//</span><span class="token number">2</span>
        k <span class="token operator">=</span> k <span class="token operator">-</span> k<span class="token operator">//</span><span class="token number">2</span>
    
    <span class="token keyword">if</span> a_begin<span class="token operator">&lt;</span><span class="token builtin">len</span><span class="token punctuation">(</span>a<span class="token punctuation">)</span><span class="token punctuation">:</span>
        <span class="token keyword">return</span> a<span class="token punctuation">[</span>a_begin<span class="token operator">+</span>k<span class="token number">-1</span><span class="token punctuation">]</span>
    <span class="token keyword">else</span><span class="token punctuation">:</span>
        <span class="token keyword">return</span> b<span class="token punctuation">[</span>b_begin<span class="token operator">+</span>k<span class="token number">-1</span><span class="token punctuation">]</span>

递归做法

import numpy as np
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        m = len(nums1)
        n = len(nums2)
        if (m+n)%2 :
            return self.find(nums1,0,nums2,0,(m+n)//2+1)
        else:
            return (self.find(nums1,0,nums2,0,(m+n)//2) + self.find(nums1,0,nums2,0,(m+n)//2+1))/2

<span class="token keyword">def</span> <span class="token function">find</span><span class="token punctuation">(</span>self<span class="token punctuation">,</span> a<span class="token punctuation">,</span> a_begin<span class="token punctuation">,</span>b<span class="token punctuation">,</span>b_begin<span class="token punctuation">,</span>k<span class="token punctuation">)</span><span class="token punctuation">:</span>
    <span class="token keyword">if</span> a_begin<span class="token operator">&gt;=</span><span class="token builtin">len</span><span class="token punctuation">(</span>a<span class="token punctuation">)</span><span class="token punctuation">:</span>
        <span class="token keyword">return</span> b<span class="token punctuation">[</span>b_begin<span class="token operator">+</span>k<span class="token number">-1</span><span class="token punctuation">]</span>
    <span class="token keyword">if</span> b_begin<span class="token operator">&gt;=</span><span class="token builtin">len</span><span class="token punctuation">(</span>b<span class="token punctuation">)</span><span class="token punctuation">:</span>
        <span class="token keyword">return</span> a<span class="token punctuation">[</span>a_begin<span class="token operator">+</span>k<span class="token number">-1</span><span class="token punctuation">]</span>
    <span class="token keyword">if</span> k<span class="token operator">==</span><span class="token number">1</span> <span class="token punctuation">:</span>
        <span class="token keyword">return</span> <span class="token builtin">min</span><span class="token punctuation">(</span>a<span class="token punctuation">[</span>a_begin<span class="token punctuation">]</span><span class="token punctuation">,</span>b<span class="token punctuation">[</span>b_begin<span class="token punctuation">]</span><span class="token punctuation">)</span>
    a_k <span class="token operator">=</span> a<span class="token punctuation">[</span>a_begin <span class="token operator">+</span> k<span class="token operator">//</span><span class="token number">2</span> <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token keyword">if</span> a_begin <span class="token operator">+</span> k<span class="token operator">//</span><span class="token number">2</span> <span class="token operator">-</span> <span class="token number">1</span> <span class="token operator">&lt;</span> <span class="token builtin">len</span><span class="token punctuation">(</span>a<span class="token punctuation">)</span> <span class="token keyword">else</span> <span class="token number">100000</span>
    b_k <span class="token operator">=</span> b<span class="token punctuation">[</span>b_begin <span class="token operator">+</span> k<span class="token operator">//</span><span class="token number">2</span> <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token keyword">if</span> b_begin <span class="token operator">+</span> k<span class="token operator">//</span><span class="token number">2</span> <span class="token operator">-</span> <span class="token number">1</span> <span class="token operator">&lt;</span> <span class="token builtin">len</span><span class="token punctuation">(</span>b<span class="token punctuation">)</span> <span class="token keyword">else</span> <span class="token number">100000</span> 
        
    <span class="token keyword">if</span> a_k <span class="token operator">&lt;</span> b_k<span class="token punctuation">:</span>
        <span class="token keyword">return</span> self<span class="token punctuation">.</span>find<span class="token punctuation">(</span>a<span class="token punctuation">,</span>a_begin<span class="token operator">+</span>k<span class="token operator">//</span><span class="token number">2</span><span class="token punctuation">,</span>b<span class="token punctuation">,</span>b_begin<span class="token punctuation">,</span>k<span class="token operator">-</span>k<span class="token operator">//</span><span class="token number">2</span><span class="token punctuation">)</span>
    <span class="token keyword">else</span><span class="token punctuation">:</span>
        <span class="token keyword">return</span> self<span class="token punctuation">.</span>find<span class="token punctuation">(</span>a<span class="token punctuation">,</span>a_begin<span class="token punctuation">,</span>b<span class="token punctuation">,</span>b_begin<span class="token operator">+</span>k<span class="token operator">//</span><span class="token number">2</span><span class="token punctuation">,</span>k<span class="token operator">-</span>k<span class="token operator">//</span><span class="token number">2</span><span class="token punctuation">)</span>