标签: median

如何找到2个排序的阵列A和B的中值,它们分别是长度为m和n.我搜索过,但大多数算法都假设两个数组的大小相同.我想知道我们怎么能找到中位数,如果m!= n考虑例子,A = {1,3,5,7,11,15}其中m = 6,B = {2,4,8,12,14}其中n = 5,中位数为7

任何帮助表示赞赏.我正准备接受采访,现在我正在努力解决这个问题.

我有一组相互不同的元素(x_1,x_2,...,x_n).每个元素都有一个正值(w_1,w_2,...,w_n).这些正值的总和为1.

我必须找到一个Optimal元素(x_k),它是:

和

我发现这个算法:

proc OptimalElement(arr[])
 prevs_w := 0
 nexts_w := 0

 for (i = 0; i <= n; i++)
 {
   wi := arr[i].w

   nexts_w := 1 - prevs_w - wi

   IF (prevs_w < 0,5 && nexts_w <= 0,5) THEN
     return arr[i]
   ELSE
     prevs_w := prevs_w + wi
   ENDIF
 }
end

但是该算法仅比较索引为i <k且i> k的项的总和.但我需要算法来计算x_i <x_k和x_i> x_k的项目总和.

算法应该有O(n)时间.你知道怎么解决吗？Thx提示.

输入示例:

x_i | 1; 4; 2; 3; 5
w_i | 0,1; 0,2; 0,3; 0,2; 0,2

编写T ComputeMedian() const在O(n)时间内计算树中值的函数的实现.假设树是BST但不一定是平衡的.回想一下n个数的中值定义如下:如果n是奇数,则中值是x,使得小于x的值的数量等于大于x的值的数量.如果n是偶数,则一加上小于x的值的数量等于大于x的值的数量.例如,给定数字8,7,2,5,9,中位数为7,因为有两个小于7的值和两个大于7的值.如果我们将3加到集合中,则中位数变为5.

这是二叉搜索树节点的类:

template <class T>
class BSTNode
{
public:
BSTNode(T& val, BSTNode* left, BSTNode* right);
~BSTNode();
T GetVal();
BSTNode* GetLeft();
BSTNode* GetRight();

private:
T val;
BSTNode* left;
BSTNode* right;  
BSTNode* parent; //ONLY INSERT IS READY TO UPDATE THIS MEMBER DATA
int depth, height;
friend class BST<T>;
};

二进制搜索树类:

template <class T>
class BST
{
public:
BST();
~BST();

bool Search(T& val);
bool Search(T& val, BSTNode<T>* node);
void Insert(T& val);
bool DeleteNode(T& val);

void BFT(void);
void PreorderDFT(void);
void …

所以我想这在技术上不是一个代码问题，但我确信在编写代码时会为其他人和我自己提出这个问题，所以希望它仍然是一个很好的发布在 SO 上的问题。

谷歌已经指导我对何时使用一个或另一个财务数字以及诸如此类的事情进行了很多很好的冗长解释。

但是我的特定上下文不适合，我想知道这里是否有人有一些见解。我需要对特定项目的“好”程度进行大量个人用户的投票。即，一定数量的用户各自给特定项目打分 0 到 10 之间，我想报告“典型”分数是多少。将几何和/或算术平均值报告为典型响应的直观原因是什么？

或者，就此而言，我最好报告中位数吗？

我想“最好”的方法可能涉及一些心理学......

无论如何，你有它。

谢谢！

我正在寻找一个快速/有效的中值滤波器的Ansi C实现.有什么指针吗？

到目前为止,我已经找到了以下实现,这很好,但我对更快的实现感到好奇.我只需要一维.

我的主要目标是从浮动的巨大矩阵计算中位数(按列).例:

a = numpy.array(([1,1,3,2,7],[4,5,8,2,3],[1,6,9,3,2]))

numpy.median(a, axis=0)

Out[38]: array([ 1.,  5.,  8.,  2.,  3.])

矩阵太大而不适合Python内存(~5 TB),所以我将它保存在csv文件中.所以我想遍历每一列并计算中位数.

有没有办法让我在不读取整个文件的情况下获取列迭代器？

关于计算矩阵中值的任何其他想法也会很好.谢谢!

我正在尝试返回一系列流式数字的运行中位数。为此，我使用最大堆（将值存储在系列的下半部分）和最小堆（将值存储在系列的上半部分）。

特别是，我正在使用来自heapq模块（https://docs.python.org/2/library/heapq.html）的Python（2.0）内置的min-heap数据结构。相反，要构建最大堆，我只需使用需要推入堆中的数字的负数即可。

我的Python代码如下：

import heapq

maxh = []
minh = []
vals=[1,2,3,4,5,6,7,8,9,10]
for val in vals:

    # Initialize the data-structure and insert/push the 1st streaming value
    if not maxh and not minh:
        heapq.heappush(maxh,-val)
        print float(val)
    elif maxh:

        # Insert/push the other streaming values
        if val>-maxh[0]:
            heapq.heappush(minh,val)
        elif val<-maxh[0]:
            heapq.heappush(maxh,-val)

        # Calculate the median
        if len(maxh)==len(minh):
            print float(-maxh[0]+minh[0])/2
        elif len(maxh)==len(minh)+1:
            print float(-maxh[0])
        elif len(minh)==len(maxh)+1:
            print float(minh[0])

        # If min-heap and max-heap grow unbalanced we rebalance them by
        # removing/popping …

我在这个论坛上看到了一些关于应用带有移动窗口的中值滤波器的讨论，但我的应用程序有一个特殊的特性。

我有一个尺寸为750x12000x10000的 3D 数组，我需要应用一个中值滤波器来生成一个 2D 数组（12000x10000）。为此，每个中值计算都应考虑固定的邻域窗口（通常为100x100）和所有 z 轴值。矩阵中有一些零值，在计算中位数时不应考虑它们。为了处理真实数据，我使用numpy.memmap：

fp = np.memmap(filename, dtype='float32', mode='w+', shape=(750, 12000, 10000))

为了处理使用 memmap 存储的真实数据，我的输入数组被细分为几个块，但为了提高我的测试速度，我将在这篇文章中使用一个减少的数组(11, 200, 300)和一个较小的窗口(11, 5, 5)或 (11, 50, 50) 并且我期望结果矩阵 (200, 300)：

import numpy as np
from timeit import default_timer as timer

zsize, ysize, xsize = (11, 200, 300)
w_size = 5 #to generate a 3D window (all_z, w_size, w_size)
#w_size = 50 #to generate a 3D window (all_z, w_size, w_size) …

这是一个算法问题：

输入是具有非重复正整数的数组。查找具有最大中值的连续子数组（大小> 1）。

示例：输入：[100、1、99、2、1000]，输出应为（1000 + 2）/ 2 = 501的结果

我可以提出强力解决方案：尝试从2->数组大小的所有长度中找到最大中值。但这似乎太慢了。我也尝试在此问题上使用两个指针，但不确定何时向左和向右移动指针。

有谁有更好的主意来解决这个问题？

我需要生成一个数百万行的滑动窗口并计算第 3 列的中位数。我的数据看起来像这样，第 1 列始终相同，第 2 列等于行号，第 3 列是我需要中位数的信息为了：

HiC_scaffold_1  1   34
HiC_scaffold_1  2   34
HiC_scaffold_1  3   36
HiC_scaffold_1  4   37
HiC_scaffold_1  5   38
HiC_scaffold_1  6   39
HiC_scaffold_1  7   40
HiC_scaffold_1  8   40
HiC_scaffold_1  9   40
HiC_scaffold_1  10  41
HiC_scaffold_1  11  41
HiC_scaffold_1  12  41
HiC_scaffold_1  13  44
HiC_scaffold_1  14  44
HiC_scaffold_1  15  55

我需要这样的结果，假设滑动窗口为 4 并四舍五入到最接近的整数。在真实数据集中，我可能会使用 1000 的滑动窗口：

HiC_scaffold_1  4   35
HiC_scaffold_1  5   37
HiC_scaffold_1  6   38
HiC_scaffold_1  7   39
HiC_scaffold_1  8   40
HiC_scaffold_1  9   40
HiC_scaffold_1  10  40 …