cod*_*ver 43 arrays algorithm logic
我试图找到5个排序数组的中位数的解决方案.这是一个面试问题.
我能想到的解决方案是合并5个数组,然后找到中位数[O(l + m + n + o + p)].
我知道对于2个相同大小的排序数组,我们可以在log(2n)中完成.[通过比较两个阵列的中位数,然后丢弃每个阵列的一半并重复该过程]...查找中位数可以是排序数组中的常量时间..所以我认为这不是log(n)？..这个时间复杂度是多少？
1] 5个阵列是否有类似的解决方案.如果阵列大小相同,那么有更好的解决方案吗？
2]我假设因为要求5,N排序数组会有一些解决方案吗？
谢谢你的任何指示.
我向采访者回答的一些澄清/问题:
长度相同的数组
=>不,
我猜数组的值会有重叠
=>是
作为练习,我认为2个阵列的逻辑没有扩展.这是一个尝试:
应用2个数组的上述逻辑说3个数组:[3,7,9] [4,8,15] [2,3,9] ...中位数7,8,3
投掷元素[ 3,7,9] [4,8] [3,9] ..中位数7,6,6
投掷元素[3,7] [8] [9] ..medians 5,8,9 ...
投掷元素[7] [8] [9] ..中位数= 8 ......这似乎不正确吗？
排序元素的合并=> [2,3,4,7,8,9,15] =>预期中位数= 7
Nem*_*emo 26
(这是对两个数组的想法的概括.)
如果你从五个阵列中的五个中位数开始,显然总体中位数必须在五个中位数中最小和最大之间.
证明是这样的:如果a是中位数的最小值,并且b是中位数的最大值,那么每个数组的元素少于一半,而小于a的元素少于一半.结果如下.
所以在包含a的数组中,丢弃小于a的数字; 在包含b的数组中,丢弃大于b的数字......但是只丢弃两个数组中相同数量的元素.
也就是说,如果a是来自其数组开头的j个元素,并且b是来自其数组末尾的k个元素,则会丢弃数组中的第一个min(j,k)元素和最后一个min(j,k) b)数组中的元素.
迭代直到你总共减少1或2个元素.
这些操作中的每一个(即,找到排序数组的中值并从数组的开头或结尾丢弃k个元素)是恒定时间.所以每次迭代都是恒定的时间.
每次迭代都会丢弃(超过)至少一个数组中的一半元素,并且您只能对五个数组中的每一个执行log(n)次...所以整个算法是log(n).
[更新]
正如Himadri Choudhury在评论中指出的那样,我的解决方案是不完整的; 有很多细节和角落需要担心.所以,要把事情搞得一团糟......
对于五个数组R中的每一个,将其"下中位数"定义为R [n/2-1],将其"上中位数"定义为R [n/2],其中n是数组中元素的数量(和数组)从0开始索引,除以2舍入).
让"a"成为下中位数中最小的,而"b"是上位中位数中最大的.如果有多个具有最小下中位数的阵列和/或具有最大上中位数的多个阵列,则从不同的阵列中选择a和b(这是其中一个极端情况).
现在,借用Himadri的建议:从其数组中删除所有元素,包括 a,以及从其数组中包含 b的所有元素,注意从两个数组中删除相同数量的元素.注意a和b可以在同一个数组中; 但如果是这样,它们就不能具有相同的值,因为否则我们就可以从不同的数组中选择其中一个.所以如果这个步骤结束了从同一个数组的开始和结束丢弃元素,那就没关系了.
只要您有三个或更多阵列就可以迭代.但是,一旦你只有一两个阵列,你必须改变你的战略,而不是包容; 你只删除但不包括 a和down,但不包括 b.只要剩下的一个或两个数组都至少有三个元素(保证你取得进展),就像这样继续.
最后,您将减少到几种情况,其中最棘手的是剩下两个数组,其中一个有一个或两个元素.现在,如果我问你:"给定一个排序的数组加上一个或两个额外的元素,找到所有元素的中位数",我认为你可以在恒定的时间内做到这一点.(同样,有很多细节可以解决,但基本的想法是,向数组中添加一个或两个元素并不会"非常推动中位数".)