精华内容
下载资源
问答
  • 题目:在一个文件中有 10G 个整数,乱序排列,要求找出中位数。内存限制为 2G。只写出思路即可(内存限制为 2G的意思就是,可以使用2G的空间来运行程序,而不考虑这台机器上的其他软件的占用内存)。关于中位数:数据...

    题目:在一个文件中有 10G 个整数,乱序排列,要求找出中位数。内存限制为 2G。只写出思路即可(内存限制为 2G的意思就是,可以使用2G的空间来运行程序,而不考虑这台机器上的其他软件的占用内存)。

    关于中位数:数据排序后,位置在最中间的数值。即将数据分成两部分,一部分大于该数值,一部分小于该数值。中位数的位置:当样本数为奇数时,中位数=(N+1)/2 ; 当样本数为偶数时,中位数为N/2与1+N/2的均值(那么10G个数的中位数,就第5G大的数与第5G+1大的数的均值了)。

    分析:明显是一道工程性很强的题目,和一般的查找中位数的题目有几点不同。

    1. 原数据不能读进内存,不然可以用快速选择,如果数的范围合适的话还可以考虑桶排序或者计数排序,但这里假设是32位整数,仍有4G种取值,需要一个16G大小的数组来计数。

    2. 若看成从N个数中找出第K大的数,如果K个数可以读进内存,可以利用最小或最大堆,但这里K=N/2,有5G个数,仍然不能读进内存。

    3. 接上,对于N个数和K个数都不能一次读进内存的情况,《编程之美》里给出一个方案:设k

    解法:首先假设是32位无符号整数。

    1. 读一遍10G个整数,把整数映射到256M个区段中,用一个64位无符号整数给每个相应区段记数。

    说明:整数范围是0 - 2^32 - 1,一共有4G种取值,映射到256M个区段,则每个区段有16(4G/256M = 16)种值,每16个值算一段, 0~15是第1段,16~31是第2段,……2^32-16 ~2^32-1是第256M段。一个64位无符号整数最大值是0~8G-1,这里先不考虑溢出的情况。总共占用内存256M×8B=2GB。

    2. 从前到后对每一段的计数累加,当累加的和超过5G时停止,找出这个区段(即累加停止时达到的区段,也是中位数所在的区段)的数值范围,设为[a,a+15],同时记录累加到前一个区段的总数,设为m。然后,释放除这个区段占用的内存。

    3. 再读一遍10G个整数,把在[a,a+15]内的每个值计数,即有16个计数。

    4. 对新的计数依次累加,每次的和设为n,当m+n的值超过5G时停止,此时的这个计数所对应的数就是中位数。

    总结:

    1.以上方法只要读两遍整数,对每个整数也只是常数时间的操作,总体来说是线性时间。

    2. 考虑其他情况。

    若是有符号的整数,只需改变映射即可。若是64为整数,则增加每个区段的范围,那么在第二次读数时,要考虑更多的计数。若过某个计数溢出,那么可认定所在的区段或代表整数为所求,这里只需做好相应的处理。噢,忘了还要找第5G+1大的数了,相信有了以上的成果,找到这个数也不难了吧。

    3. 时空权衡。

    花费256个区段也许只是恰好配合2GB的内存(其实也不是,呵呵)。可以增大区段范围,减少区段数目,节省一些内存,虽然增加第二部分的对单个数值的计数,但第一部分对每个区段的计数加快了(总体改变??待测)。

    4. 映射时尽量用位操作,由于每个区段的起点都是2的整数幂,映射起来也很方便。

    posted on 2010-04-13 09:22 海大哥 阅读(221) 评论(0)  编辑  收藏

    展开全文
  • 最近工作需要 要求把python的代码写成java版本,python中有一个np.median()求中位数的方法,java决定手写一个先说说什么是中位数中位数就是中间的那个数,如果一个集合是奇数个,那么中位数就是按大小排列后,最...

    最近工作需要 要求把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 total = new ArrayList();

    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 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()方法转换后传入

    补充知识:Java计算中位数、方差、标准差、众数

    我就废话不多说了,大家还是直接看代码吧~

    import java.text.DecimalFormat;

    import java.util.*;

    /**

    * 数学算法(数学算法(方差、标准差、中位数、众数))

    * @author

    *

    */

    public class MathAlgorithm {

    private final static double dmax = 999;// Double.MAX_VALUE;//Double类型的最大值,太大的double值,相乘会达到无穷大

    private final static double dmin = Double.MIN_VALUE;// Double类型的最小值

    private final static int n = 100;// 假设求取100个doubl数的方差和标准差

    public static void main(String[] args) {

    Random random = new Random();

    double[] x = new double[n];

    for (int i = 0; i < n; i++) {// 随机生成n个double数

    x[i] = Double.valueOf(Math.floor(random.nextDouble() * (dmax - dmin)));

    System.out.println(x[i]);

    }

    // 设置doubl字符串输出格式,不以科学计数法输出

    DecimalFormat df = new DecimalFormat("#,##0.00");// 格式化设置

    // 计算方差

    double dV = getVariance(x);

    System.out.println("方差=" + df.format(dV));

    // 计算标准差

    double dS = getStandardDiviation(x);

    System.out.println("标准差=" + df.format(dS));

    int[] intArr={5,10,15,8,6};

    System.out.println(Arrays.toString(intArr)+" 中位数:"+median(intArr));

    int[] intArr2={5,10,15,8,6,7};

    System.out.println(Arrays.toString(intArr2)+" 中位数:"+median(intArr2));

    int[] arr = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 1, 2, 2, 3, 4, 5};

    List modalNums = getModalNums(arr);

    System.out.println("众数:"+modalNums);

    float[] arr2 = {0.1f, 1.1f, 2.1f, 3.1f, 4.1f, 5.1f, 6.1f, 7.1f, 8.1f, 9.1f, 10.1f, 1.1f, 1.1f, 2.1f, 2.1f, 3.1f, 4.1f, 5.1f};

    List modalNums2 = getModalNums(arr2);

    System.out.println("众数:"+modalNums2);

    }

    /**

    * 方差s^2=[(x1-x)^2 +...(xn-x)^2]/n

    * @param x

    * @return

    */

    public static double getVariance(double[] x) {

    int m = x.length;

    double sum = 0;

    for (int i = 0; i < m; i++) {// 求和

    sum += x[i];

    }

    double dAve = sum / m;// 求平均值

    double dVar = 0;

    for (int i = 0; i < m; i++) {// 求方差

    dVar += (x[i] - dAve) * (x[i] - dAve);

    }

    return dVar / m;

    }

    /**

    * 标准差σ=sqrt(s^2)

    * @param x

    * @return

    */

    public static double getStandardDiviation(double[] x) {

    int m = x.length;

    double sum = 0;

    for (int i = 0; i < m; i++) {// 求和

    sum += x[i];

    }

    double dAve = sum / m;// 求平均值

    double dVar = 0;

    for (int i = 0; i < m; i++) {// 求方差

    dVar += (x[i] - dAve) * (x[i] - dAve);

    }

    return Math.sqrt(dVar / m);

    }

    /**

    * 中位数(int)

    * @param nums: A list of integers.

    * @return: An integer denotes the middle number of the array.

    */

    public static int median(int []nums){

    if(nums.length==0)

    return 0;

    int start=0;

    int end=nums.length-1;

    int index=partition(nums, start, end);

    if(nums.length%2==0){

    while(index!=nums.length/2-1){

    if(index>nums.length/2-1){

    index=partition(nums, start, index-1);

    }else{

    index=partition(nums, index+1, end);

    }

    }

    }else{

    while(index!=nums.length/2){

    if(index>nums.length/2){

    index=partition(nums, start, index-1);

    }else{

    index=partition(nums, index+1, end);

    }

    }

    }

    return nums[index];

    }

    private static int partition(int nums[], int start, int end){

    int left=start;

    int right=end;

    int pivot=nums[left];

    while(left

    while(left=pivot){

    right--;

    }

    if(left

    nums[left]=nums[right];

    left++;

    }

    while(left

    left++;

    }

    if(left

    nums[right]=nums[left];

    right--;

    }

    }

    nums[left]=pivot;

    return left;

    }

    /**

    * 中位数(float)

    * @param nums: A list of integers.

    * @return: An integer denotes the middle number of the array.

    */

    public static float median(float []nums){

    if(nums.length==0)

    return 0;

    int start=0;

    int end=nums.length-1;

    int index=partition(nums, start, end);

    if(nums.length%2==0){

    while(index!=nums.length/2-1){

    if(index>nums.length/2-1){

    index=partition(nums, start, index-1);

    }else{

    index=partition(nums, index+1, end);

    }

    }

    }else{

    while(index!=nums.length/2){

    if(index>nums.length/2){

    index=partition(nums, start, index-1);

    }else{

    index=partition(nums, index+1, end);

    }

    }

    }

    return nums[index];

    }

    private static int partition(float nums[], int start, int end){

    int left=start;

    int right=end;

    float pivot=nums[left];

    while(left

    while(left=pivot){

    right--;

    }

    if(left

    nums[left]=nums[right];

    left++;

    }

    while(left

    left++;

    }

    if(left

    nums[right]=nums[left];

    right--;

    }

    }

    nums[left]=pivot;

    return left;

    }

    /**

    * 众数(int)

    * 众数:在一个数组中出现次数最多的数

    * 如果存在多个众数,则一起返回

    * @param arr

    * @return

    */

    public static List getModalNums(int[] arr) {

    int n = arr.length;

    if (n == 0) {

    return new ArrayList();

    }

    if (n == 1) {

    return Arrays.asList(arr[0]);

    }

    Map freqMap = new HashMap<>();

    for (int i = 0; i < n; i++) { // 统计数组中每个数出现的频率

    Integer v = freqMap.get(arr[i]);

    // v == null 说明 freqMap 中还没有这个 arr[i] 这个键

    freqMap.put(arr[i], v == null ? 1 : v + 1);

    }

    // 将 freqMap 中所有的键值对(键为数,值为数出现的频率)放入一个 ArrayList

    List> entries = new ArrayList<>(freqMap.entrySet());

    // 对 entries 按出现频率从大到小排序

    Collections.sort(entries, new Comparator>() {

    @Override

    public int compare(Map.Entry e1, Map.Entry e2) {

    return e2.getValue() - e1.getValue();

    }

    });

    List modalNums = new ArrayList<>();

    modalNums.add(entries.get(0).getKey()); // 排序后第一个 entry 的键肯定是一个众数

    int size = entries.size();

    for (int i = 1; i < size; i++) {

    // 如果之后的 entry 与第一个 entry 的 value 相等,那么这个 entry 的键也是众数

    if (entries.get(i).getValue().equals(entries.get(0).getValue())) {

    modalNums.add(entries.get(i).getKey());

    } else {

    break;

    }

    }

    return modalNums;

    }

    /**

    * 众数(float)

    * 众数:在一个数组中出现次数最多的数

    * 如果存在多个众数,则一起返回

    * @param arr

    * @return

    */

    public static List getModalNums(float[] arr) {

    int n = arr.length;

    if (n == 0) {

    return new ArrayList();

    }

    if (n == 1) {

    return Arrays.asList(arr[0]);

    }

    Map freqMap = new HashMap<>();

    for (int i = 0; i < n; i++) { // 统计数组中每个数出现的频率

    Integer v = freqMap.get(arr[i]);

    // v == null 说明 freqMap 中还没有这个 arr[i] 这个键

    freqMap.put(arr[i], v == null ? 1 : v + 1);

    }

    // 将 freqMap 中所有的键值对(键为数,值为数出现的频率)放入一个 ArrayList

    List> entries = new ArrayList<>(freqMap.entrySet());

    // 对 entries 按出现频率从大到小排序

    Collections.sort(entries, new Comparator>() {

    @Override

    public int compare(Map.Entry e1, Map.Entry e2) {

    return e2.getValue() - e1.getValue();

    }

    });

    List modalNums = new ArrayList<>();

    modalNums.add(entries.get(0).getKey()); // 排序后第一个 entry 的键肯定是一个众数

    int size = entries.size();

    for (int i = 1; i < size; i++) {

    // 如果之后的 entry 与第一个 entry 的 value 相等,那么这个 entry 的键也是众数

    if (entries.get(i).getValue().equals(entries.get(0).getValue())) {

    modalNums.add(entries.get(i).getKey());

    } else {

    break;

    }

    }

    return modalNums;

    }

    }

    以上这篇java 计算中位数的实现方法就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持聚米学院。

    展开全文
  • 最近工作需要 要求把python的代码写成java版本,python中有一个np.median()求中位数的方法,java决定手写一个先说说什么是中位数中位数就是中间的那个数,如果一个集合是奇数个,那么中位数就是按大小排列后,最...

    最近工作需要 要求把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 total = new ArrayList();

    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 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()方法转换后传入

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

    千次阅读 2019-01-04 15:51:14
    最近工作需要 要求把python的代码写成java版本,python中有一个np.median()求中位数的方法,java决定手写一个 先说说什么是中位数中位数就是中间的那个数, 如果一个集合是奇数个,那么中位数就是按大小排列...

    最近工作需要 要求把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()方法转换后传入

    展开全文
  • //"9.2"的9表示输出的长度,2表示小数点后的位数。 System.out.printf("%+9.2f",d);//"+"表示输出的带正负号。 System.out.printf("%-9.4f",d);//"-"表示输出的左对齐(默认为右对齐)。 System.out.printf("%+-...
  • 键盘的扫描输入、包的调用、多位数倒序输出、多位数取余运算package com.bdqn.test;import java.util.Scanner;public class Person {public static void main(String[] args) {Scanner input =new Scanner(System.in...
  • 现在 有10亿个int型的数字(JAVA中 int 型占4B),以及一台可用内存为1GB的机器,如何找出这10亿个数字的中位数中位数定义:数字排序之后,位于中间的那个数。比如将10亿个数字进行排序(位置从1到10亿),排序之后,...
  • LeetCode4:给定两个大小为 m 和 n 的...示例 1:nums1 = [1, 3]nums2 = [2]则中位数是 2.0示例 2:nums1 = [1, 2]nums2 = [3, 4]则中位数是 (2 + 3)/2 = 2.5解法一:将两个数组合并后找中位数。class Solution {publ...
  • 主要介绍了java 计算中位数的实现方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
  • Javajava 数字 转 String 固定位数 不足补零 String.format("%04d", 22); //25为int型 //打印 0022 0代表前面要补的字符 4代表字符串长度 d表示参数为整数类型
  • 我正在计算由文本字段接收的输入填充的数组的总数,平均值和中位数。我已经设法计算出总计和平均值,我只是不能让中位数工作。我认为数组需要排序才能做到这一点,但我不知道如何做到这一点。这是问题,还是还有另外...
  • 如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert...
  • 背景:在做接口开发时,遇到一个需求是将...首先,想到的是#java中限制小数点的位数#,查到了以下的解决方案: Double dev=1.2999; DecimalFormat df = new DecimalFormat("#.00");// 保留五小数非四舍五入型 ...
  • 展开全部 /** * @param args */ public static void main(String[] args) { Scanner in = ... } 因为是多位数,也不知道多少位,所32313133353236313431303231363533e78988e69d8331333337613838以用大数类型。
  • java中小数点位数问题

    2016-03-19 23:59:50
    double num = 3.1415926;  double n = 3;    DecimalFormat d = new DecimalFormat("#.00");  System.out.println(d.format(n));  System.out.println(d.format(num));
  • Java中控制输出位数

    千次阅读 2019-01-29 13:01:58
    import java.math.BigDecimal; import java.text.DecimalFormat; import java.text.NumberFormat; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new S....
  • JAVA中生成指定位数随机数的方法很多,下面列举几种比较常用的方法。方法一、通过Math类1 public static String getRandom1(intlen) {2 int rs = (int) ((Math.random() * 9 + 1) * Math.pow(10, len - 1));3 return...
  • JavaStudy35:中位数

    2019-09-21 23:51:23
    JavaStudy35:中位数 总时间限制: 2000ms 内存限制: 65536kB 描述 中位数定义:一组数据按从小到大的顺序依次排列,处在中间位置的一个数或最中间两个数据的平均值(如果这组数的个数为奇数,则中位数为位于...
  • java 商业保留有效位数和小数位数

    千次阅读 2018-01-19 11:59:29
    之前,我曾写过一篇 java使用BigDecimal 处理商业精度及高精度详解,如何去获取有效位数;当时的我,没有弄清楚有效和小数位数其实是互斥的! 导致在之后的工作业务出现了问题; 今天特意记录下; 问题的主要...
  • 41.1 数据流中的中位数 题目描述 如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后...
  • java中保留任意位数的小数/java中四舍五入/获得任意位数的方法 /java中double类型保留小数位数 、 float保留小数位数
  • 本人正在自学Java,有些编程题要求输出小数时保留n小数,想请问各位大神们,在Java中有哪些可以实现以固定精度输出小数的方法?方法最好给多一些并且给出示例代码,谢谢。
  • Java中控制小数位数

    千次阅读 2014-03-12 16:41:40
    方法一:使用BigDecimal public class BigDecimalDemo { public static void main(String[] args) { BigDecimal decimal = new BigDecimal(Math.PI); decimal = decimal.setScale(10, BigDecimal.ROUND_HALF_...
  • Java实现-中位数

    万次阅读 2017-06-18 14:48:42
    中位数是排序后数组的中间值,如果数组的个数是偶数个,则返回排序后数组的第N/2个数。 您在真实的面试中是否遇到过这个题?  Yes 样例 给出数组[4, 5, 1, 2, 3], 返回 3 给出数组[7, 9, 4, ...
  • 如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。 思路:定义一...
  • Java中数字保留两小数

    万次阅读 2019-05-20 15:22:44
    Java中数字保留小数Double类型数据处理Double类型数据转String处理 Double类型数据处理 下列代码表示保留两小数并且四舍五入的双精度类型数据处理。 Double num = 69.26345; BigDecimal bd = new BigDecimal(num);...
  • Java中有效值位数控制

    千次阅读 2016-03-12 21:37:07
    大家都知道在Java中,double及single的位数都很长,比如2.2121112333212333。有时候我们实在不希望以这种变态的格式输出。我们可以通过以下方法指定输出的格式: import java.text.DecimalFormat; public class ...
  • import java.math.BigDecimal; import java.math.MathContext;... * JAVA中关于数字取几有效位数,和小数点后保留几小数的小示例。 * @author SailingZhao * */ public class TestBigDecimal { /**保留几
  • Java语言怎么计算一个数组中所有数字的中位数呢 要用代码完整写出来给我看看

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 15,190
精华内容 6,076
关键字:

java中位数

java 订阅