查找没有数据结构的中位数

Question

(我的代码是用Java编写的,但问题是不可知的;我只是在寻找算法的想法)

所以这就是问题所在:我创建了一个方法,只需找到数据集的中位数(以数组的形式给出).这是实施:

public static double getMedian(int[] numset) {
    ArrayList<Integer> anumset = new ArrayList<Integer>();
    for(int num : numset) {
        anumset.add(num);
    }
    anumset.sort(null);

    if(anumset.size() % 2 == 0) {
        return anumset.get(anumset.size() / 2);
    } else {
        return (anumset.get(anumset.size() / 2)
                   + anumset.get((anumset.size() / 2) + 1)) / 2;
    }
}

我去学校的老师然后挑战我写一个方法再次找到中位数,但没有使用任何数据结构.这包括任何可以容纳多个值的东西,所以包括字符串,任何形式的数组等等.我花了很长时间试图想出一个想法,我很难过.有任何想法吗？

Answer 1

该任务的通常算法是Hoare的Select算法.这非常类似于快速排序,除了在快速排序中您在分区后递归排序两半,但对于select,您只在包含感兴趣项目的分区中执行递归调用.

例如,让我们考虑这样的输入,我们将在其中找到第四个元素:

[7,1,17,21,3,12,0,5]

我们将任意使用第一个元素(7)作为我们的支点.我们最初将它拆分为(带有标记为*的枢轴:

[1,3,0,5,]*7,[17,21,12]

我们正在寻找第四个元素,而7是第五个元素,所以我们然后分区(仅)左侧.我们将再次使用第一个元素作为我们的支点,给出(使用{和}标记我们现在忽略的输入部分).

[0] 1 [3,5] {7,17,21,12}

1 最终成为第二个元素,所以我们需要将项目分区到右边(3和5):

{0,1} 3 [5] {7,17,21,12}

使用3作为枢轴元素,我们最终没有向左和5向右.3是第三个元素,所以我们需要向右看.这只是一个元素,因此(5)是我们的中位数.

通过忽略未使用的一侧,这降低了从排序的O(n log n)到仅O(N)的复杂性[虽然我稍微滥用了符号 - 在这种情况下我们处理预期的行为,而不是最坏的案例,正如大O通常所做的那样].

如果你想保证良好的行为(以牺牲平均速度稍慢为代价),还有一个中位数算法算法.

这提供了保证的O(N)复杂性.