精华内容
下载资源
问答
  • 如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。

    问题:如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。

    分析:

    数据时从一个数据流中读出来的,数据的数目随着时间的变化而增加。如果用一个数据容器来保存从流中读出来的数据,当有新的数据从流中读出来时,这些数据就插入到数据容器中。用什么样的数据结构比较合适呢?我们可以先分析下:

    一是没有排序的数组。很容易想到的是用Partition函数找到数组中的中位数。这样一来的话,插入一个数字和找出中位数的时间复杂度是O(1)和O(n)。

    二是排序的数组。但是插入操作的时间复杂度是O(n),由于是排好序的数组,所以找到中位数是一个简单的操作,只需要时间复杂度为O(1)。

    三是排序的链表。需要O(n)时间才能在链表中找到合适的位置插入新的数据。之前我们讨论过采用两个指针指向链表中间结点,那么可以在O(1)时间找到中位数。这样一来,时间效率与基于排序的数组的时间效率是一样的。

    四是二叉搜索树。可以将把插入新数据的平均时间降到O(nlogn),但是问题是当二叉搜索树极度不平衡的时候看起来像一个排序的链表,插入新数据的时间将是O(n)。为了得到中位数,可以在二叉树结点中添加一个表示子树结点数目的字段。凭借这个字段,可以在平均时间O(nlogn)时间得到中位数,但最坏的情况仍然需要O(n)时间。

    五是利用平衡的二叉树,即AVL树。AVL树的平衡因子定义是左右子树的高度差,为找到中位数,我们可以把AVL树的平衡因子定义为左右子树结点数目之差。这样一来可以在O(nlogn)时间内往AVL树添加一个新结点,同时用O(1)时间得到我们需要的中位数。可以说AVL树的效率是最高的,但在短时间内编写其代码不是件容易的事。

    六是最大堆和最小堆结合。如果数据在容器中已经排序,那么中位数可以由P1和P2指向的数得到,如果容器中数据的数目是奇数,那么P1和P2指向同一个数据。如下图所示:

    如图整个数据容器分隔成两个部分,位于容器左边部分的数据比右边的数据小,P1指向的数据是左边部分最大的数,P2指向的数据是右边部分最小的数。如果我们能够保证数据容器左边的数据都小于右边的数据,这样即使左右两边内部的数据没有排序,也可以根据左边最大数和右边最小数得到中位数。所以自然想到的是用一个最大堆实现左边的数据容器,用最小堆实现右边的数据容器。这样一来,可以在O(nlogn)时间内添加一个新结点,同时用O(1)时间得到我们需要的中位数。在分析上我们必须起码满足两个基本保证:一是保证数据平均分配到两个堆中,因此两个堆中数据的数目之差不能超过1,所以在数据总数目是偶数时把新数据插入到最小堆中或最大堆中;二是保证最大堆里的所有数据都小于最小堆中所有的数据。编写代码时,要仔细考虑。

    不同数据结构的比较如下:


    综上,采用最大堆和最小堆相结合的方案是性价比最高。

    import java.util.*;


    public class Solution{
    int count;
    PriorityQueue minHeap = new PriorityQueue();
    @SuppressWarnings("unchecked")
    PriorityQueue maxHeap = new PriorityQueue(11, new Comparator() {


    @Override
    public int compare(Object o1, Object o2) {
    // TODO Auto-generated method stub
    // PriorityQueue默认是小顶堆,实现大顶堆,需要反转默认排序器
    return ((Integer) o2).compareTo((Integer) o1);
    }
    });


    public void Insert(Integer num) {
    count++;
    if ((count & (0x1)) == 0) { // 判断偶数的高效写法


    if (!maxHeap.isEmpty() && num < (Integer) maxHeap.peek()) {
    maxHeap.offer(num);
    num = (Integer) maxHeap.poll();


    }


    minHeap.offer(num);


    } else {
    if (!minHeap.isEmpty() && num > (Integer) minHeap.peek()) {
    minHeap.offer(num);
    num = (Integer) minHeap.poll();


    }


    maxHeap.offer(num);


    }


    }


    public Double GetMedian() {
    if (count == 0) {
    throw new RuntimeException("no available number!");
    }
    // 总数为奇数时,大顶堆堆顶就是中位数
    double result;
    if ((count & (0x1)) == 1) {
    result = Double.parseDouble(maxHeap.peek() + "");
    }


    else {
    result = (Double.parseDouble(minHeap.peek() + "") + Double
    .parseDouble(maxHeap.peek() + "")) / 2.0;
    }


    return result;


    }
    }


    展开全文
  • 注意EXCEL中位数问题 中位数奇数个还是偶数个 不能用and的原因 两种方法

    1 如果要 取得C列c4:c18 符合初级,且去掉空值的 中位数

    • median
    • 如果只需要取,符合 初级 这种单条件的中位数
    • =MEDIAN(IF(B:B=E4,C:C))

     

    • 如果需要多条件,符合条件1:初级,且符合条件2:去掉空值
    • 可以用下面两种方法实现
    • =MEDIAN(IF(($B$4:$B$18=E4)*($C$4:$C$18>0),$C$4:$C$18))
    • 条件 true*true 表示and  (true在数值运算里作为1,false作为0)
    • 如果 true+true 表示 or 
    • =MEDIAN(IF($C$4:$C$18*($B$4:$B$18=E4),$C$4:$C$18))
    • 在数值运算里
    • $C$4:$C$18 空值会当false处理,也是一样效果

     

     

    2 注意点,多条件不能用 if(and()) 而是用 条件*条件 或 条件+条件

    • IF($A:$A=G$3) 或 IF ($B:$B=$F4) 都将返回一个由TRUE或FALSE组成的数组。
    • 用*或其它四则运算符号运算时,TRUE被当作1参与,FALSE被当作0参与。
    • 只有两个都是1时,才会得到1。
    • 所以这里乘的意思是与AND一样的,但它可以保留数组,不象AND只能返回单值。
    • 如果不用乘,而用加,那么意思就是两个条件中只要任一符合,就符合。相当于“或”。
    • SUM(IF(($A:$A=G$3)+($B:$B=$F4),$C:$C))

     

    3 不能用and的原因:因为and只能返回1个值,不能返回一个内存数组

    而数组公式不能用一个值作数组的中间步骤

    • and返回的是一个值,而不是一个内存数组
    • 数组公式,输入的内容是数组,中间结果也是数组,输出可以被普通函数转化为 数组 或 单个值。

     

     

    4 因为是数组公式,数组要精确,不能随便的用 a:a 这种,而是要精确到数组

    • 因为数组公式,处理数组,必须要精确
    • 如  a:a 表示整个A列数组
    • 而a4:a18只是这一段精确的数组

     

    5 注意EXCEL中位数问题

    • 中位数,奇数个还是偶数个
    • 如果数组元素是偶数个,EXCEL的median返回的是 中间2个数的均值。。。

     

     

    6 例子2:求1列中,大于10,但是小于20之间的多个数的median,sum

     

    • MEDIAN(IF((A2:A16>=10)*(A2:A16<=20),A2:A16))
    • SUM(IF((A2:A16>=10)*(A2:A16<=20),A2:A16))

     

    展开全文
  • java 计算中位数方法

    万次阅读 2019-01-04 15:51:14
    如果一个集合是奇数个,那么中位数就是按大小排列后,最中间那个数, 如果一个集合是偶数个,那么中位数就是按大小排列后,最中间那2个数的平均数。 比如: 1,2,3,4,5 那中位数就是3 1,2,3,4...

    最近工作需要 要求把python的代码写成java版本,python中有一个np.median()求中位数的方法,java决定手写一个

    先说说什么是中位数:

    中位数就是中间的那个数,

    如果一个集合是奇数个,那么中位数就是按大小排列后,最中间那个数,

    如果一个集合是偶数个,那么中位数就是按大小排列后,最中间那2个数的平均数。

    比如:

    1,2,3,4,5  那中位数就是3

    1,2,3,4,5,6 那中位数就是 (3+4)/2 = 3.5

    知道逻辑后方法就很简单了 下面是代码

    public static void main(String[] args) {
    	List<Integer> total = new ArrayList<Integer>();
    	total.add(4);
    	total.add(2);
    	total.add(3);
    	total.add(1);
    	total.add(5);
    	total.add(6);
    	double a = median(total);
    	System.out.println(a);
    }
    private static double median(List<Integer> total) {
    	double j = 0;
    	//集合排序
        Collections.sort(total);
        int size = total.size();
        if(size % 2 == 1){
        	j = total.get((size-1)/2);
        }else {
        	//加0.0是为了把int转成double类型,否则除以2会算错
        	j = (total.get(size/2-1) + total.get(size/2) + 0.0)/2;
        }
    	return j;
    }

    1. 方法内先判断集合是奇数还是偶数,如果是奇数那么就是第n+1/2个数 ,也就是下标为n-1/2的值,

    如果是偶数 就是第n/2和n/2+1的数的平均值 也就是下标为n/2-1和n/2的平均值

    2. 该方法传入的是list集合  如果为数组  可以先用Arrays.aslist()方法转换后传入

    展开全文
  • 如果数组有偶数个元素,中位数就是最中间的两个数值的平均数。中位数对于了解“我的值是否位于中间?”非常有用。比如,我在学校的最后一次考试中得了 D (或 80),那么我的在全班同学中的排名是否在前 50%?举一个具体...

    什么是中位数?

    数值型数组的中位数是在数据排序后位于数组中间项的值。如果数组有偶数个元素,中位数就是最中间的两个数值的平均数。

    中位数对于了解“我的值是否位于中间?”非常有用。比如,我在学校的最后一次考试中得了 D (或 80),那么我的在全班同学中的排名是否在前 50%?

    举一个具体的例子,我们看看从学校的这些测试分数中找到中位数的过程:[55, 80, 95, 100, 99, 70, 60]。

    首先,对数组排序:[55, 80, 95, 100, 99, 70, 60] ===> [55, 60, 70, 80, 95, 99, 100].

    这个数组包含 7 个元素,不是偶数,所以中位数是 (7 / 2 + 1),即第 4 项的值 => 80。

    在 MySQL 中计算某列数据的中位数

    很不幸,MySQL 并未内置计算列数据中位数的函数。因此,我们需要自己创建查询。

    假如我们想从“grades”列中查找中位数。来看看我们要创建的查询是什么算法:

    对“grades”排序并为排序后的每一行附加序号(行号)

    如果总行数是奇数,找到位于有序列表中间位置的值。

    如果总行数是偶数,找到位于有序列表中间两个位置的值。

    计算上面第 (3) 步和第 (4) 取得值的平均值。

    返回这个平均值,它就是中位数。

    那么这样的查询该怎么写?

    SET@rownum := -1;

    SELECT

    AVG(g.grade)

    FROM

    (SELECT@rowindex:=@rowindex + 1ASrowindex,

    grades.grade ASgrade

    FROMgrades

    ORDERBYgrades.grade)ASg

    WHERE

    t.rowindex IN(FLOOR(@rowindex / 2) , CEIL(@rowindex / 2));

    解释一下:

    先从内部的一个子查询开始 —— 为 @rowindex 赋值的子查询会为每个成绩赋予一个自增后的序号,并对 grades 排序 [译者注:按逻辑和代码是先排序再赋予序号]。

    有了排好序的成绩列表之后,外层查询会获取位中间位置的值。如果数组元素是奇数个,两个值都是取的位于正中那个值。

    然后,外层查询的 SELECT 子句返回上述两个值的平均值作为中位数。

    你看,这并不是简单的运行 MEDIAN(column_name),但它可行。我们期待 MySQL 会决定将这一功能添加到内置产品中,这将简化获取中位数的查询。

    展开全文
  • 在所有的N位数,有多少个数中偶数个数字3(说明,0是偶数)? 【输入格式】 读入一个N 【输出格式】 输出有多少个数中偶数个数字3。 【输入样例】 2 【输出样例】 73(由于 位数 比较大的情况下,导致输出数据...
  • 中位数

    千次阅读 2013-03-19 10:23:57
    当变量值的项数N为奇数时,处于中间位置的变量值即为中位数;当N为偶数时,中位数则为处于中间位置的2个变量值的平均数。 中位数的作用  中位数的作用与算术平均数相近,也是作为所研究数据的代表值。在一个等差...
  • 3.5 备忘 4 最长公共子序列 5 最优二叉搜索树 6 中位数和顺序统计量 6.1 最小值最大值 6.2 期望为线性时间的选择算法 6.3 最坏情况为线性时间的选择算法 0 动态规划与分治法 动态规划(dynamic programming)与分治...
  • 给定一段连续的整数,求出他们所有偶数的平方以及所有奇数的立方. 输入 输入数据包含多组测试实例,每组测试实例包含一行,由两个整数mn组成. 输出量 对于每组输入数据,输出一行,应包括两个整数xy,分别...
  • 请运用运算写程序找出这两个只出现奇数的数字。本篇问题涉及到位运算的相关知识,其中涉及到对位运算的内容不太熟悉大家可进入以下网址温故一下。https://blog.csdn.net/qq_57985909/article/details/119154619 ...
  • #include int main(int argc, const char * argv[]) { ... printf("请输入一个:");   scanf("%d",&a);  //方法一,求余   if (a%2)  {   printf("奇数!\n");  }
  • 四分位数计算方法总结

    万次阅读 2019-12-21 20:16:54
    1、数列项为奇数时: 3、5、9、11、17、19、35 先计算位置,在通过位置计算对应的数值 Q1:(n+1)*0.25=2 Q2:(n+1)*0.5=4 Q3:(n+1)*0.75=6 当下标正好为整数时,对应的数值为Q1=5、Q2=11、Q3=19 3、5、9...
  • //获取一个二进制序列所有的偶数位和奇数位,分别输出二进制序列。  首先需要了解一个知识点:获取二进制n的对应i位置的二进制,只需(n &gt;&gt; i)&amp; 1  解题思路:  1&gt; ...
  • /*题目:一个数组有两种出现了奇数次,其他都出现了偶数次,怎么找到这两个*/ /* 常用算法之提取二进制最右侧的1: 例如 获取 二进制 010010101000 最右侧的1,即获得 000000001000 解法:利用公式 ...
  • 大数据求中位数(插值计算)

    千次阅读 2020-06-15 11:48:24
    在学数学时我们学到过求中位数的方法,在数据个数为偶数时找最中间的两个数然后求平均数如果数据个数为奇数时则只需找数据个数一半的那位上的数字即可代表中位数(前提是数组是有序的) java代码如下: public ...
  • JS实现一个求中位数的函数middle

    千次阅读 2019-05-02 15:05:35
    function middle(){ let args=[...arguments];... if(args.length%2===0){ //判断数字个奇数还是偶数 return ((args[args.length/2]+args[args.length/2-1])/2);//偶数个取中间两个的平均 ...
  • Leetcode 4.寻找两个正序数组的中位数 ...另外就是,对于偶数和奇数中位数的计算方法不同。 对于长度为n的正序数组nums,这里方便公式表达,假设数组下标从1开始。如果n是偶数,那中位数为**(nums[n/2]+nums[n/2
  • #define _CRT_SECURE_NO_WARNINGS #include&amp;amp;amp;amp;lt;stdio.h&amp;amp;amp;amp;gt; #include&amp;amp;amp;amp;lt;stdlib.h&...奇数分之一都是正值,偶数分之一都是负值 for(i=1;
  • 均值、中位数中位数的概念以及优缺点对比。偏态分布难点分析,以及偏度、峰度计算公式。文末附相关学习链接。
  • 这个实例解决问题是:计算一天的每个小时,网上新增多少条评论,并计算这些评论的平均长度。代码如下:
  • 其中你可以在里面选奇数个元素或者偶数个元素 然后其实两种选的情况种是一样的 当然,偶数个元素可以选0个 用公式写就是 第一种证明首先我们可以分三种情况第一种情况n=0 显然。。 当选偶数个时,可以...
  • 编写程序,输入一个长整型正数,判断该数是几位数 #include#includemain(){\x09longintx;\x09inti=0;printf("input:");\x09scanf("%ld",&x);do{x=x/10;i++;\x C语言题:编写一个程序,输入长方形的长和宽,计算长方形的...
  • SQL 如何计算每个分组的中位数

    千次阅读 2020-05-22 18:35:28
    如果数据个数是奇数中位数就是最中间位置那个值;如果是偶数,则是中间位置那两个数的平均值。 怎么查询出数据分组以后每个组的中位数呢? 用SQL来解决这个问题是很有难度的! SQL的集合是无序的,没有数据位置...
  • 展开全部有点复杂,在你基础上加了条有奇数的数据创建表,插入数据:62616964757a686964616fe58685e5aeb931333363396338createtabletest(cat_idint,priceint);insertintotestvalues(101,90);insertintotestvalues...
  • 请你找出并返回这两个正序数组的 中位数 。 示例 1: 输入:nums1 = [1,3], nums2 = [2] 输出:2.00000 解释:合并数组 = [1,2,3] ,中位数 2 示例 2: 输入:nums1 = [1,2], nums2 = [3,4] 输出:2.50000 ...
  • 四分位数的数学计算以及使用pandas计算前言参考举例1(奇数个)第一四分位数(下四分位数)中位数第三四分位数(上四分位数)举例2(偶数个)第一四分位数(下四分位数)中位数第三四分位数(上四分位数) ...
  • 度量数据中心趋势的各种方法。假设我们有某个属性X,如salary,已经对一个数据对象集记录...中心趋势度量包括均值、中位数、众数中列数。数据集“中心”的最常用、最有效的数值度量是(算术)均值。令x1,x2,…,x...
  • 利用中位数的位次特征解法2:利用升序与降序的差值解法2.1:延伸问题参考文章合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容...
  •  中位数:分类数据组的中间值(如果数据个数为偶数,则是两个中间数值的一半)  众数:数据组中出现次数最多的值(或者一组值)   异常值:比几乎其他所有数字都要 大/小 很多的数值   加权平均值:对变量在...
  • 请你找出并返回这两个正序数组的 中位数 。 示例 1: 输入:nums1 = [1,3], nums2 = [2] 输出:2.00000 解释:合并数组 = [1,2,3] ,中位数 2 示例 2: 输入:nums1 = [1,2], nums2 = [3,4] 输出:2.50000 解释:...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,441
精华内容 5,776
关键字:

偶数和奇数的中位数公式

友情链接: GHEN.rar