精华内容
下载资源
问答
  • 有序数组求中位数问题

    分享一下我老师大神的人工智能教程!零基础,通俗易懂!http://blog.csdn.net/jiangjunshow

    也欢迎大家转载本篇文章。分享知识,造福人民,实现我们中华民族伟大复兴!

                    1、有两个已排好序的数组A和B,长度均为n,找出这两个数组合并后的中间元素,要求时间代价为O(logn)。
    2、假设两个有序数组长度不等,同样的求出中位数。
    一:解析: 这个题目看起来非常简单。第一题的话: 假设数组长度为n, 那么我就把数组1和数组2直接合并,然后再直接找到中间元素。对于这样的方案,第一题和第二题就没有什么区别了。这样的话时间复杂度就是O(n)。通常在这样的情况下,那些要求比较高的面试官就会循循善诱道:“你还有更好的办法吗?” 如果比线性更高效,直接能想到的就是对数了O(log(n)),这个时间复杂度在这里可能吗? 当然还是可能的。
    算法导论上面的分析是这样的:
    Say the two arrays are sorted and increasing, namely A and B.
    It is easy to find the median of each array in O(1) time.
    Assume the median of array A is m and the median of array B is n. Then,
    1、If m==n,then clearly the median after merging is also m,the algorithm holds.
    2、If m<=n,then reserve the half of sequence A in which all numbers are greater than m,also reserve the half of sequence B in which all numbers are smaller than n.
    Run the algorithm on the two new arrays。
    3、If m>n,then reserve the half of sequence A in which all numbers are smaller than m,also reserve the half of sequence B in which all numbers are larger than n.
    Run the algorithm on the two new arrays。
    Time complexity: O(logn)
    下面,我们来画个图,分析一下这个思路:

    我们先来分析看看: 想到对数的效率,首先想到的就是二分查找,对于这个题目二分查找的意义在哪里呢?
    我们找到了A[n/2] 和 B[n/2]来比较,
    1、如果他们相等,那样的话,我们的搜索结束了,因为答案已经找到了A[n/2]就肯定是排序后的中位数了。
    2、如果我们发现B[n/2] > A[n/2],说明什么,这个数字应该在 A[n/2]->A[n]这个序列里面, 或者在 B[1]-B[n/4]这里面。 或者,这里的或者是很重要的, 我们可以说,我们已经成功的把问题变成了在排序完成的数组A[n/2]-A[n]和B[0]-B[n/2]里面找到合并以后的中位数, 显然递归是个不错的选择了。
    3、如果B[n/2] < A[n/2]呢?显然就是在A[0]-A[n/2]和B[n/2]-B[n]里面寻找了。

    在继续想, 这个递归什么时候收敛呢?当然一个case就是相等的值出现, 如果不出现等到这个n==1的时候也就结束了。
    照着这样的思路, 我们比较容易写出如下的代码, 当然边界的值需要自己思量一下(递归代码如下):
    // 两个长度相等的有序数组寻找中位数int Find_Media_Equal_Length(int a[] , int b[] , int length){    if(length == 1)    {        return a[0] > b[0] ? b[0] : a[0];    }    int mid = (length-1)/2;   //奇数就取中间的,偶数则去坐标小的    if(a[mid] == b[mid])        return a[mid];    else if(a[mid] < b[mid])    {        return Find_Media_Equal_Length(&a[length-mid-1] , &b[0] , mid+1);    //偶数则取剩下的length/2,奇数则取剩下的length/2+1        //return Find_Media_Equal_Length(a+length-mid-1 , b , mid+1);    }    else    {        return Find_Media_Equal_Length(&a[0] , &b[length-mid-1] , mid+1);        //return Find_Media_Equal_Length(a , b+length-mid-1 , mid+1);    }}
    非递归代码如下:
    // 非递归代码int Find_Media_Equal_Length(int a[] , int b[] , int length)int mid; while(1) {  if(length == 1)  {   return a[0] > b[0] ? b[0] : a[0];  }  mid = (length-1)/2;  if(a[mid] == b[mid])   return a[mid];  else if(a[mid] < b[mid])   a = a + length - mid - 1;    // a数组的后半部分  else   b = b + length - mid - 1;    // b数组的后半部分  length = mid + 1; }}
    二:马上有人说那不定长的怎么办呢?一样的,我们还是来画个图看看:

    一样的, 我们还是把这个两个数组来比较一下,不失一般性,我们假定B数组比A数组长一点。A的长度为n, B的长度为m。比较A[n/2]和B[m/2] 时候。类似的,我们还是分成几种情况来讨论:
    a、如果A[n/2] == B[m/2],那么很显然,我们的讨论结束了。A[n/2]就已经是中位数,这个和他们各自的长度是奇数或者偶数无关。
    b、如果A[n/2]  <   B[m/2],那么,我们可以知道这个中位数肯定不在[A[0]---A[n/2])这个区间内,同时也不在[B[m/2]---B[m]]这个区间里面。这个时候,我们不能冲动地把[A[0]---A[n/2])和[B[m/2]---B[m]]全部扔掉。我们只需要把[B[m-n/2]---B[m]]和[A[0]---A[n/2])扔掉就可以了。(如图所示的红色线框),这样我们就把我们的问题成功转换成了如何在A[n/2]->A[n]这个长度为 n/2 的数组和 B[1]-B[m-n/2]这个长度为m-n/2的数组里面找中位数了,问题复杂度即可下降了。
    c、只剩下A[n/2] > B[m/2],和b类似的,我们可以把A[n/2]->A[n]这块以及B[1]->B[n/2]这块扔掉了就行,然后继续递归。
    我们也可以写出如下的代码:
    // 两个长度不相等的有序数组寻找中位数int Find_Media_Random_Length(int a[] , int lengtha , int b[] , int lengthb)int mida = lengtha/2int midb = lengthb/2int l = (mida <= midb) ? mida : midb; if(lengtha == 1) {  if(lengthb % 2 == 0)  {   if(a[0] >= b[midb])    return b[midb];   else if(a[0] <= b[midb-1])    return b[midb-1];   return a[0];  }  else   return b[midb]; } else if(lengthb == 1) {  if(lengtha % 2 == 0)  {   if(b[0] >= a[mida])    return a[mida];   else if(b[0] <= a[mida-1])    return a[mida-1];   return b[0];  }  else   return a[mida]; } if(a[mida] == b[midb])  return a[mida]; else if(a[mida] < b[midb])  return Find_Media_Random_Length(&a[mida] , lengtha-l , &b[0] , lengthb-l); else  return Find_Media_Random_Length(&a[0] , lengtha-l , &b[midb] , lengthb-l);}
    举例如下:
    A:1、2、8、9、10
    B:1、2、3、4、11
    第一次:
    A:1、2、{8}、9、10
    B:1、2、{3}、4、11
    因为8>3,所以第二次:
    A:1、{2}、8
    B:3、{4}、11
    因为2<4,所以第三次:
    A:{2}、8
    B:{3}、4
    因为2<3,所以第四次:
    A:{8}
    B:{3}

    再举一个简单的例子:
    A: 1 3 5 7 9
    B: 2 4 6 8 10
    结果我们都知道是5(下中位数)。
    第一步:取5 和 6比较,发现5<6,则在 7 9 2 4中寻找吗?
    偶数的情况类似:
    A: 1 3 5 7 9 11
    B: 2 4 6 8 10 12
    第一步:取5 和 6比较,发现5<6,则在 7 9 11 2 4中寻找吗?
    个人认为取一半的时候一定需要包含用于比较的两个中位数(无论奇偶)。
    就是说上面的两个例子第一步之后:
    在A:5 7 9    B:2 4 6中继续找
    在A:5 7 9 11    B:2 4 6中继续找
    但这样导致新的问题是:新的数组A和B数字个数不一致了!
    办法是: 在递归的过程中,当数组中的元素是偶数时,在一个数组中取上中位数,在另一个数组中取下中位数,并且在整个过程中保持不变。在哪个数组中去上中位数,就一直在那个数组中取上中位数,反之亦然。奇数时的情形依旧。
    这也就解释了为什么代码中a[mid]<b[mid] 的时候,a数组的开始位置会是: a[length-mid-1]

               

    给我老师的人工智能教程打call!http://blog.csdn.net/jiangjunshow

    这里写图片描述
    展开全文
  • Leetcode算法题:两个有序数组求中位数 要求时间复杂度为O(log(m+n)) 思路: 暴力解决:合并数组并排序,简单且一定能实现,时间复杂度O(m+n) 由于两个数组已经排好序,可一边排序一边合并,用时为第一种的一半,...

    Leetcode算法题:两个有序数组求中位数

    • 要求时间复杂度为O(log(m+n))

    思路:

    1. 暴力解决:合并数组并排序,简单且一定能实现,时间复杂度O(m+n)
    2. 由于两个数组已经排好序,可一边排序一边合并,用时为第一种的一半,时间复杂度依然为O(m+n)
    3. 由题目,只需要找中位数,即中位数两侧的元素并不需要完全排序,且两数组长度已知且有序,合并后中位数的索引是固定的,所以只要找到这一个或计算中位数的两个数的索引即可,既然为查找,可用二分查找,即可实现时间复杂度为O(log(m+n))

    解决方案:

    • 将两数组分别分为左右两部分,左侧的两部分即为包含中位数的左侧,右侧即为可能包含中位数的右侧。由于一个数组的划分位置确定,另一个数组划分位置即可确定,所以只需使用二分查找在一个数组中查找到正确的划分位置就行了。

    • 为了防止一个数组中确定界限后另一个数组的分界线数组越界,直接在取小数组作为查找目标。

    • 递归查找很简单,但是索引在边界时情况非常复杂,且python中-1索引也可以取到,花了很久才找到问题所在,因此在此记录下来。


    def findMedianSortedArrays(nums1, nums2):
    
        def mid_index(left, right):
            return (left + right) // 2
        
        # 以下称第一个数组为A,第二个数组为B
        def findMedianSortedArraysSorted(short_nums, m, long_nums, n):
            is_odd = (m + n) % 2 
            mid = (m + n - 1) // 2
            if m == 0:
                if is_odd:
                    return long_nums[mid]
                else:
                    return float(long_nums[mid] + long_nums[mid + 1]) / 2
            left = 0
            right = m - 1
            i = mid_index(left, right)
            while left <= i <= right:
                j = mid - (i + 1)
                # 若A数组左侧最大元素大于B数组右侧最小元素,中位索引左移
                if i > 0 and short_nums[i] > long_nums[j + 1]:
                    right = i
                    i = mid_index(left, right)
                # 若B数组左侧最大元素大于B数组右侧最小元素,中位索引右移
                elif i < m - 1 and long_nums[j] > short_nums[i + 1]:
                    left = i + 1
                    i = mid_index(left, right)
                # 从0索引开始查找,查找并未结束
                # 其实只有数组长度为2时才会出现这种情况
                elif i == 0 and m > 1 and long_nums[j] > short_nums[i + 1]:
                    left = i + 1
                    i = mid_index(left, right)
                # 达成结束条件
                else:
                    if i == 0:
                    	# 该数组最小值比在另一个数组中可能的中位值大
                    	# 即整个数组所有元素都应该放在右侧
                        if short_nums[i] > long_nums[j + 1]:
                            max_left = long_nums[j + 1]
                            if j + 3 <= n:
                                min_right = min(short_nums[i], long_nums[j + 2])
                            else:
                                min_right = short_nums[i]
                        else:
                        	# 只出现在两个只有一个元素,且A数组元素小于B数组元素的情况下
                        	# 应该可以合并到其他情况中,但是脑子不够用了,希望有人可以提意见
                            if j == -1:
                                max_left = short_nums[i]
                                min_right = long_nums[j + 1]
                            else:
                                max_left = max(short_nums[i], long_nums[j])
                                if m > 1:
                                    min_right = min(short_nums[i + 1], long_nums[j + 1])
                                else:
                                    min_right = long_nums[j + 1]
                    # 检索到了最后一个元素
                    elif i == m - 1:
                    	# 大坑,两数组等长时,检索到末端时j的值为-1
                    	# python列表的-1索引可以取到最后一个元素,debug才找到问题
                        if j == -1:
                            max_left = short_nums[i]
                            min_right = long_nums[j + 1]
                        # A数组最大值小于B数组中位数
                        elif short_nums[i] < long_nums[j]:
                            max_left = long_nums[j]
                            min_right = long_nums[j + 1]
                        else:
                            max_left = max(short_nums[i], long_nums[j])
                            min_right = long_nums[j + 1]
                    # 在中间位置找到正确的中位数
                    else:
                        max_left = max(short_nums[i], long_nums[j])
                        min_right = min(short_nums[i + 1], long_nums[j + 1])
                    if is_odd:
                        return max_left
                    else:
                        return float(max_left + min_right) / 2
        a = len(nums1)
        b = len(nums2)
        if a > b:
            return findMedianSortedArraysSorted(nums2, b, nums1, a)
        else:
            return findMedianSortedArraysSorted(nums1, a, nums2, b)
    

    展开全文
  • 两个有序数组求中位数问题; 这个题有很多方法: 方法一:排序,找到中位数; 方法二:归并排序的思想 方法三:转换成求第k小值 */ /* 思路:使用二分查找,时间复杂度为log(m+n). 该方法的核心是将原...
    /*
    两个有序数组求中位数问题;
    这个题有很多方法:
    方法一:排序,找到中位数;
    方法二:归并排序的思想
    方法三:转换成求第k小值  
    */


    /*
    思路:使用二分查找,时间复杂度为log(m+n). 该方法的核心是将原问题转变成
    一个寻找第k小数的问题(假设两个原序列升序排列),
    这样中位数实际上是第(m+n)/2小的数。所以只要解决了第k小数的 问题,
    原问题也得以解决。首先假设数组A和B的元素个数都大于k/2,
    我们比较A[k/2-1]和B[k/2-1]两个元素,这两个元素分别表示A的第k /2小的元素
    和B的第k/2小的元素。这两个元素比较共有三种情况:>、<和=。
    如果A[k/2-1]<B[k/2-1],这表示 A[0]到A[k/2-1]的元素都在A和B合并之后的前k小的元素中。
    换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将 其抛弃。
    */
    #include<iostream>


    using namespace std;


    double findKth(int a[], int m, int b[], int n, int k)
    {
    if (m>n)
    {
    return findKth(b,n,a,m,k);
    }


    if (m==0)
    {
    return b[k-1];
    }
    if (k==1)
    {
    return min(a[0], b[0]);
    }


    int pa = min(k/2, m);
    int pb = k - pa;
    if (a[pa-1]<b[pb-1])
    {
    return findKth(a+pa, m-pa, b,  n, k-pa);
    }
    else if (a[pa-1]>b[pb-1])
    {
    return findKth(a, m, b+pb, n-pb, k-pb);
    }
    else
    {
    return a[pa-1];
    }
    }


    class Solution
    {
    double findMedian(int A[], int m, int B[], int n)
    {
    int total = m + n;
    if (total&0x1)
    {
    return findKth(A, m, B, n, total/2+1);
    }
    else
    {
    return (findKth(A, m, B, n, total / 2) + findKth(A,m,B,n,total/2+1))/2;
    }
    }
    };
    展开全文
  • 在网上看了很多两个等长有序数组求中位数的文章,但我都觉得有点儿问题。等下会说我觉得问题在哪里。 先说下中位数定义:当数组元素个数为奇数个的时候,中位数就是中间的数字,比如数组[1,2,3,4,5],那么3就是中位...

    在网上看了很多两个等长有序数组求中位数的文章,但我都觉得有点儿问题。等下会说我觉得问题在哪里。

    先说下中位数定义:当数组元素个数为奇数个的时候,中位数就是中间的数字,比如数组[1,2,3,4,5],那么3就是中位数。如果数组元素个数为偶数个的时候,那么中间两个元素的平均值就是中位数的值,比如数组[1,2,4,5],那么中位数就是(2+4)/2=3.

    定义清楚了下面就来说下两个等长数组求中位数的问题,为了简化问题,直接假设两个数组都按从小到大顺序排列好了。两个等长数组,那么总的元素个数肯定为偶数,那么结果就肯定是某两个数字的平均值。

    求解方法基本都一样,就是用二分搜索的思路来做。假设有两个数组A,B,首先用两个指针a,b分别指向A,B中间的数字,然后比较这两个数字,假设a指向数字大于b的数字,那么结果肯定不在a指向数字的右边和b指向数字的左边。然后分别向左向右移动a,b两个指针,再次进行比较。就是二分搜索的思路。

    然后说问题,在网上看了好多博客,求得的结果都是指针移动的最后结果是A中某一元素和B中某一元素一起作为结果。但我认为这是不对的,因为最终结果的两个数字完全可以在同一个数组中,假设有两个数组

    A:1 2 7 9 10
    B:3 4 5 6 8
    合并后中位数应该是5 和 6,两个数都在数组B中,并不是A、B各一个数。

    网上很多人写的迭代结束条件都是找到了a=b或者最后子数组长度都为1,我觉得结束条件应该是找到a=b或者数组长度为2。

    可能对于这个问题有点儿钻牛角尖了,思路大家基本都差不多,只是我在迭代的结束条件上和大家看法不太一样,也许我考虑的有问题,希望各位批评指正。

    以下是实现代码:

    #include <stdio.h>


    void findMedian(int first[],int second[],int length);


    int result[4];//因为是迭代为2的时候结束,所以会有4个数字对于四个数字应该还排下序,然后取中间两个,这里直接打印输出
    int main(void){
    int first[]={1,2,3,6,11};
    int second[]={4,7,8,10,12};
    findMedian(first,second,5);//随便写的两个数组例子
    printf("%d  %d  %d  %d\n",result[0],result[1],result[2],result[3]);//
    }

    void findMedian(int first[],int second[],int length){
    if(length<=2){
    result[0]=first[0];
    result[1]=first[1];
    result[2]=second[0];
    result[3]=second[1];
    }
    int low1=0,low2=0,high1=length-1,high2=length-1;
    int current1,current2,k1,k2;
    while(length>2){
    current1=(low1+high1)/2;
    current2=(low2+high2)/2;
    if(first[current1]==second[current2]){
    printf("The median is %d\n",first[current1]);

     //因为主函数中有输出,所以这里就赋了下值

    result[0]=first[current1];

    result[1]=first[current1];
    result[2]=first[current1];
    result[3]=first[current1];

    return;
    }
    else if(first[current1]>second[current2]){

    //k1 k2表示当前指针和边界的距离,因为存在奇偶问题,所以k1和k2不一定相同,指针移动时候要移动二者中较小的距离
    k1=high1-current1;
    k2=current2-low2;
    if(k1==k2){
    high1=current1;
    low2=current2;
    length-=k1;
    }
    else if(k1>k2){
    high1=current1+1;
    low2=current2;
    length-=k2;
    }
    else{
    high1=current1;
    low2=current2-1;
    length-=k1;
    }
    }
    else{
    k1=current1-low1;
    k2=high2-current2;
    if(k1==k2){
    high2=current2;
    low1=current1;
    length-=k1;
    }
    else if(k1>k2){
    low1=current1-1;
    high2=current2;
    length-=k2;
    }
    else{
    high2=current2+1;
    low1=current1;
    length-=k1;
    }
    }
    }

    result[0]=first[low1];
    result[1]=first[high1];
    result[2]=second[low2];
    result[3]=second[high2];
    }

    展开全文
  • package leetcode4; import java.util.ArrayList; import java.util.HashSet; import java.util.TreeSet;... * 请你找出这两个有序数组中位数,并且要求算法的时间复杂度为 O(log(m + n))。 *...
  • 算法题:两个有序数组求中位数

    千次阅读 2019-03-21 15:49:57
    数组A,B分别有序,我们可以先找到数组A中的一条分界线i,使得数组A分为A_left,和A_right两部分,那么因为时要找到中位数,我们可以直接计算出B数组的一条分界线j,使得size(Aleft)+size(Bleft)=size(Aright)+size...
  • 链接:https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/4-xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-shu/ 来源:力扣(LeetCode)
  • 对于长度为L的有序数组,它的中位数是(a[ceil((L+1)/2)]+a[floor((L+1)/2)])/2 算法原理: 类似三分法极值 两个人都前进,谁前进之后比较小,就让谁前进。 import math class Solution(object): def findpos...
  • 测试样例个 while (N-- ) { l1 = vector(rand() % 4 + 1 ); l2 = vector(rand() % 4 + 1 ); for (auto & i : l2) { i = rand() % 100 ;; } for (auto & i : l1) { i = rand() % 100 ;...
  • 2、假设两个有序数组长度不等,同样的中位数。一:解析: 这个题目看起来非常简单。第一题的话: 假设数组长度为n, 那么我就把数组1和数组2直接合并,然后再直接找到中间元素。对于这样的方案,第一题和第二题就...
  •   这个题目简单来说就是如果将两个已经排序的数组合并为一个虚拟数组出这个虚拟数组中位数即可。 解题思路:   1、这道题最主要的就是切(cut),怎么将数组切成合适的两段是关键,对于一个数组来说在...
  • #include &lt;iostream&gt; using namespace std; int get_median(int a[],int begin1,int end1,int b[],int begin2,int end2,int k){...end1){ //在数组A无法找到 return get_median(b,begin2,end2,...
  • 有序数组中求第N大,求中位数题目解答 两个有序数组找相同的数字没想法,感觉只想到建立一个哈希表,然后另一个数组去查查自己在不在哈希表中,有序的话还可以利用下元素大小,如果查到的某个元素已经大于了第一个...
  • Leecode两个有序数组中位数 题目 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。 请找出这两个有序数组中位数。要求算法的时间复杂度为 O(log (m+n)) 。 示例 1:nums1[1,3]nums2[2]中位数:2.0 示例 2:...
  • 请你找出这两个有序数组中位数,并且要求算法的时间复杂度为O(log(m + n))。 例如: nums1 = [1, 3] nums2 = [2] 则中位数是 2.0 nums1 = [1, 2] nums2 = [3, 4] 则中位数是 (2 + 3)/2 = 2.5 算法解析: 中位...
  • 寻找两个有序数组中位数

    万次阅读 2020-03-12 15:22:22
      之前讲解过一道数据流求中位数的题目,但是仔细一想觉得那一次对几种数据结构简单的分析了一下实现,并没有对中位数的题目做一个凝练总结,这一次借这个机会,好好整理一下思路。 题目描述   给定两个大小为 m...
  • 找出并返回这两个正序数组中位数 时间复杂度O(log(m+n)) 解法:二分法查找 public class Main { public static void main(String[] args) { Solution solution = new Solution(); int[] nums1 = {1,3,7,9...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 538
精华内容 215
关键字:

有序数组求中位数