Java教程

算法实验1-4查找两个有序数组合并之后的中位数

本文主要是介绍算法实验1-4查找两个有序数组合并之后的中位数，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

插个题：在解决这个算法题之前，先看一下冒泡排序：
借个大佬的图：
在这里插入图片描述
对于冒泡，是相邻两个元素比较，大的数向后移，每循环一次就确定一个“最大的数”，排在最后，下一次比较时就不用再排了，所以代码的第二个for循环是n-i-1。

步入正题
问题：

设两个长度分别为m和n的有序数组a[0:m-1]和b[0:n-1]，请使用分治策略找出这两个有序数组合并之后的中位数

算法思路：由于两个数组合并之后的中位数，比较nums1和nums2的中位数a,b，若a<b，则合并数组的中位数在a的右边，b的左边。若a>b，则合并数组的中位数在a的左边，b的右边。此题采用的是二分查找类似，此题对应的二分的终止条件是：是某个数组小到无法继续二分的时候。这是因为，每次二分剔除掉的是更少的那个部分。因此，在终止条件中，查找范围应该是一个大数组和一个只有 1～2 个元素的小数组。这样就需要根据大数组的奇偶性和小数组的数量。
终止条件 分为了5个可能性：（1）如果 a, b都只剩一个元素࿰

这篇关于算法实验1-4查找两个有序数组合并之后的中位数的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航