五个已排序数组的中位数

Question

五个已排序数组的中位数

arraysalgorithmlogic

45

我正在尝试找到五个已排序数组的中位数解决方案。这是一个面试问题。

我能想到的解决方法是合并这5个数组，然后找到中位数[O(l+m+n+o+p)]。

我知道对于长度相同的两个排序数组，我们可以在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] ..中位数5,8,9 ...
丢弃元素[7] [8] [9] .. 中位数=8 ... 这似乎不正确？

已排序元素的合并 => [2,3,4,7,8,9,15] => 预期中位数 = 7

- codeObserver

1

它们是否各自排序，还是每个数组也表示一个范围，在该范围内没有来自另一个数组的值？即，如果一个数组在1-5范围内有值，另一个数组是否也可能在相同的范围内有值？如果不是，则只需要确定数组的顺序（从最低到最高范围），总结所有长度，除以2得到中间元素，然后进入具有该元素的数组。 - filip-fku

感谢filip-fku。我回答了你的问题。 - codeObserver

3

这是一个臭名昭著的问题，因为这个想法相对容易，但实现起来却极其困难。对于k > 2，实现变得更加糟糕。对我来说，这不是一个好的技术面试问题。 - galactica

5个回答

1

应该很容易将相同的思路应用到5个数组中。

首先，将问题转化为更一般的问题。在N个排序数组中找到第K个元素

使用二分查找在每个排序数组中找到第(K/N)个元素，称为K1、K2... KN
Kmin = min(K1 ... KN)，Kmax = max(K1 ... KN)
丢弃所有小于Kmin或大于Kmax的元素，假设已经丢弃了X个元素。
现在通过在剩余元素中查找第(K - X)个元素来重复此过程

- Ryan Ye

二分查找本身是log(n)，而你正在进行log(n)次，因此这是O((log(n))^2)。但是你可以在O(log n)中解决这个问题 :-) - Nemo

1

每个数组都是有序的，因此您不需要使用二分搜索来查找它们的（N/K）小元素。它们只是A1 [N/K]，A2 [N/K]等。 - JeffE

我不明白1和2中Kmax有什么用处。你可能需要使用_如果0 < (K-Xₙ) < N，则找到每个序列的第一个元素中的第（K-Xₙ）个_。 - greybeard

顺便问一下，K和X是什么？ - Kumar Roshan Mehta

1

你不需要对这5个数组进行完整合并。你可以进行归并排序，直到你获得(l+n+o+p+q)/2个元素，那么你就有了中位数。

- karmakaze

3

你甚至不需要进行排序，只需要比较。你只需保存五个已排序数组的所有成员中间位置的那个元素。 - xpda

0

在一个已排序的列表中查找第k个元素可以通过二分查找来完成。

from bisect import bisect_left
from bisect import bisect_right

def kthOfPiles(givenPiles, k, count):
    '''
    Perform binary search for kth element in  multiple sorted list

    parameters
    ==========
    givenPiles  are list of sorted list
    count   is the total number of
    k       is the target index in range [0..count-1]
    '''
    begins = [0 for pile in givenPiles]
    ends = [len(pile) for pile in givenPiles]
    #print('finding k=', k, 'count=', count)
    
    for pileidx,pivotpile in enumerate(givenPiles):
        
        while begins[pileidx] < ends[pileidx]:
            mid = (begins[pileidx]+ends[pileidx])>>1
            midval = pivotpile[mid]
            
            smaller_count = 0
            smaller_right_count = 0
            for pile in givenPiles:
                smaller_count += bisect_left(pile,midval)
                smaller_right_count += bisect_right(pile,midval)
                
            #print('check midval', midval,smaller_count,k,smaller_right_count)
            if smaller_count <= k and k < smaller_right_count:
                return midval
            elif smaller_count > k:
                ends[pileidx] = mid
            else:
                begins[pileidx] = mid+1
            
    return -1

def medianOfPiles(givenPiles,count=None):
    '''
    Find statistical median
    Parameters:
    givenPiles  are list of sorted list
    '''
    if not givenPiles:
        return -1 # cannot find median
    
    if count is None:
        count = 0
        for pile in givenPiles:
            count += len(pile)
            
    # get mid floor
    target_mid = count >> 1
    midval = kthOfPiles(givenPiles, target_mid, count)
    if 0 == (count&1):
        midval += kthOfPiles(givenPiles, target_mid-1, count)
        midval /= 2
        
    return '%.1f' % round(midval,1)

上述代码还可以正确计算统计中位数。

将上述二分查找与耐心排序相结合，可以得到一种有价值的技术。

值得一提的是，选择枢轴的中位数中位数算法。它给出了近似值。我想这与我们在这里所问的不同。

- KRoy

0

使用heapq来保留每个列表的最小候选项。

先决条件：N个已排序的K长度列表

O（NKlgN）

import heapq
class Solution:
    def f1(self, AS):
        def f(A): 
            n = len(A)
            m = n // 2
            if n % 2:
                return A[m]
            else:
                return (A[m - 1] + A[m]) / 2
        res = []
        q = []
        for i, A in enumerate(AS):
            q.append([A[0], i, 0])
        heapq.heapify(q)
        N, K = len(AS), len(AS[0])
        while len(res) < N * K:
            mn, i, ii = heapq.heappop(q)
            res.append(mn)
            if ii < K - 1:
                heapq.heappush(q, [AS[i][ii + 1], i, ii + 1])
        return f(res)

    def f2(self, AS):
        q = []
        for i, A in enumerate(AS):
            q.append([A[0], i, 0])
        heapq.heapify(q)
        N, K = len(AS), len(AS[0])
        n = N * K
        m = n // 2
        m1 = m2 = float('-inf')
        k = 0
        while k < N * K:
            mn, i, ii = heapq.heappop(q)
            res.append(mn)
            k += 1
            if k == m - 1:
                m1 = mn
            elif k == m:
                m2 = mn
                return m2 if n % 2 else (m1 + m2) / 2 
            if ii < K - 1:
                heapq.heappush(q, [AS[i][ii + 1], i, ii + 1])
        return 'should not go here'

- Yang Liu

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Nemo · Accepted Answer

（这是针对两个数组的想法的推广。）

如果您首先查看五个数组的五个中位数，则显然总体中位数必须介于五个中位数中最小值和最大值之间。

证明大致如下: 如果a是中位数的最小值，b是中位数的最大值，则每个数组都少于一半的元素小于a并且少于一半的元素大于b。结论得证。

因此，在包含a的数组中，丢弃小于a的数字；在包含b的数组中，丢弃大于b的数字...但只能从两个数组中同时丢弃相同数量的元素。

也就是说，如果a距其数组开头j个元素，b距其数组末尾k个元素，则从a的数组中丢弃前min（j，k）个元素，从b的数组中丢弃后min（j，k）个元素。

迭代，直到总计剩余1或2个元素。

每个这样的操作（即找到排序数组的中位数并且从数组的开头或结尾丢弃k个元素）都是常数时间。因此，每次迭代都是常数时间。

每次迭代至少从一个数组中丢弃（超过）一半的元素，并且您每个五个数组只能对数(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但不包括a和删除至b但不包括b。只要剩余的一个或两个数组中至少有三个元素（保证您取得进展），就可以像这样继续进行。

最后，您将减少到一些情况，其中最棘手的是剩下两个数组，其中一个具有一个或两个元素。现在，如果我问你：“给定一个排序过的数组以及一个或两个附加元素，找到所有元素的中位数”，我认为您可以在常量时间内完成。（同样，还有一堆细节需要解决，但基本思想是添加一个或两个元素不会使中位数变化非常大。）