题解 | #在两个长度相等的排序数组中找到上中位数#

在两个长度相等的排序数组中找到上中位数

http://www.nowcoder.com/practice/6fbe70f3a51d44fa9395cfc49694404f

奇数数组

比如 1 2 3 8 9和 -1 -2 4 5 6两个数组,找这两个数组的中位数,就是找合并排序后的第5位数字。先进行各自的mid对比,arr1的mid为3小于arr2的mid4. left1要跳到mid1。因为mid1还有可能是第五名。在arr1中比mid1小的肯定有俩了就是1 2 3 8 9,在arr2中-1 -2 4 5 6,这俩 也有可能小于mid1,所以要mid1在可能范围。 再看arr2的范围变化,分析mid2是否可能在范围中,arr1中前三个肯定小于mid2,arr2中前两个也肯定mid2,所以mid2肯定是至少第六名,所以应该是排除mid2,但是为了利用等长数组的性质,1 2 3 8 9,所以arr1范围长度变为3,所以arr2的范围长度也应该是3,所以right2=mid2。

偶数

比如 1 2 8 9和 1 3 5 6,现在找第四位,mid1<mid2,此时要让left1=mid1 + 1,分析mid1是否在可能范围:arr1中比mid1肯定小的1 2 8 9,在arr2中比mid1可能小的1 3 5 6,所以mid1最多是第三位,所以left1要在mid1基础上再向后移一位。

全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务