求一个java求中位数算法算法？

来源：蜘蛛抓取(WebSpider) 时间：2017-03-22 10:13 标签： java求中位数算法

给定一个未排序的整数数组找箌其中位数。

中位数是排序后数组的中间值如果数组的个数是偶数个，则返回排序后数组的第N/2个数

请你找出这两个有序数组的中位數并且要求算法的时间复杂度为 $O(log(m + n))$。

else { // i 为合适值根据不同情况返回不同值

  • 时间复杂度：$O(log(min(m,n)))$，首先查找的区间是 $[0, m]$。 而该區间的长度在每次循环之后都会减少为原来的一半 所以，我们只需要执行 $log(m)$ 次循环由于我们在每次循环中进行常量次数的操作，所以时間复杂度为 $O(log(m))$ 由于 $m≤n$，所以时间复杂度是 $O(log(min(m,n)))$

  • 空间复杂度：$O(1)$，我们只需要恒定的内存来存储 9 个局部变量 所以空间复杂度为 $O(1)$。

如果不是對时间复杂度的限制此题最容易想到的解法是遍历合并数字，然后取中位数

—————《明天没有你》

我要回帖

更多关于 java求中位数算法 的文章

 

随机推荐