计算中位数 - JavaScript

Question

我一直在尝试计算中位数，但似乎存在一些数学问题，因为我无法得到正确的中位数值，也无法弄清原因。这是代码；

class StatsCollector {

    constructor() {
        this.inputNumber = 0;
        this.average = 0;

        this.timeout = 19000;

        this.frequencies = new Map();
        for (let i of Array(this.timeout).keys()) {
            this.frequencies.set(i, 0);
        }
    }

    pushValue(responseTimeMs) {
        let req = responseTimeMs;
        if (req > this.timeout) {
            req = this.timeout;
        }

        this.average = (this.average * this.inputNumber + req) / (this.inputNumber + 1);

        console.log(responseTimeMs / 1000)
        let groupIndex = Math.floor(responseTimeMs / 1000);
        this.frequencies.set(groupIndex, this.frequencies.get(groupIndex) + 1);

        this.inputNumber += 1;
    }

    getMedian() {
        let medianElement = 0;
        if (this.inputNumber <= 0) {
            return 0;
        }
        if (this.inputNumber == 1) {
            return this.average
        }
        if (this.inputNumber == 2) {
            return this.average
        }
        if (this.inputNumber > 2) {
            medianElement = this.inputNumber / 2;
        }

        let minCumulativeFreq = 0;
        let maxCumulativeFreq = 0;
        let cumulativeFreq = 0;
        let freqGroup = 0;
        for (let i of Array(20).keys()) {
            if (medianElement <= cumulativeFreq + this.frequencies.get(i)) {
                minCumulativeFreq = cumulativeFreq;
                maxCumulativeFreq = cumulativeFreq + this.frequencies.get(i);
                freqGroup = i;
                break;
            }
            cumulativeFreq += this.frequencies.get(i);
        }

        return (((medianElement - minCumulativeFreq) / (maxCumulativeFreq - minCumulativeFreq)) + (freqGroup)) * 1000;
    }

    getAverage() {
        return this.average;
    }

}

当我输入以下数值时，以下是结果的快照:

342、654、987、1093、2234、6243、7087、20123

正确的结果应该是:

中位数：1663.5

- Muhammed Bayram

---

也许可以在这里查看如何在 JavaScript 中从数组中找到中位数（8个或9个值）。 - Radek Hofman

计算中位数需要对值进行排序，并选择中间的值。 - Pointy

那不是中位数。中位数应该在集合中。 - jmargolisvt

我的第一个猜测是你有一个四舍五入误差。 - victor

中位数是排序后列表的中间数字，如果值的数量为奇数，则中位数就是该数字。如果值的数量为偶数，则中位数是中间两个值的中点或平均值。 - Mark B

可能是[在JavaScript中从数组中查找中位数值（8个值或9个值）]的重复问题(https://dev59.com/UYLba4cB1Zd3GeqPfHtU)。 - str

Answer 1

将您的中位数方法更改为以下内容：

function median(values){
  if(values.length ===0) throw new Error("No inputs");

  values.sort(function(a,b){
    return a-b;
  });

  var half = Math.floor(values.length / 2);
  
  if (values.length % 2)
    return values[half];
  
  return (values[half - 1] + values[half]) / 2.0;
}

fiddle

- jdmdevdotnet

---

你不需要使用 else。 - dll

请注意，此方法会修改给定的数组。 - Akseli Palén

我认为空数组的中位数不是0，而是未定义。 - gmolau

为了保留给定的数组，在函数开头使用类似 values = [...values]; 的方法。 - Jay Dadhania

无法使用median([-0.51182868190794402, 0.33955843791573237, 1.073205764212215])。 - DavidDunham

Answer 2

这里还有另一个解决方案：

function median(numbers) {
    const sorted = Array.from(numbers).sort((a, b) => a - b);
    const middle = Math.floor(sorted.length / 2);

    if (sorted.length % 2 === 0) {
        return (sorted[middle - 1] + sorted[middle]) / 2;
    }

    return sorted[middle];
}

console.log(median([4, 5, 7, 1, 33]));

- JBallin

---

好的，这将保持原始数组不变。 - Akseli Palén

我知道我迟了2年，但这个答案比其他排在前面的答案更好。 - user13594322

缺少检查参数数组长度大于或等于两个的代码。 - Filip Ilievski

@FilipIlievski，确实假设输入是有效的。我们还可以验证输入是否实际上是一个数组（对象可以设置长度），元素是否为数字等。 - JBallin

@JBallin 是的，你说得对 :) 我来自TypeScript，所以一旦您正确定义了您的类型，就没有太多可担心的了。✌️ - Filip Ilievski

Answer 3

2023 TypeScript 方法

const median = (arr: number[]): number | undefined => {
  if (!arr.length) return undefined;
  const s = [...arr].sort((a, b) => a - b);
  const mid = Math.floor(s.length / 2);
  return s.length % 2 ? s[mid] : ((s[mid - 1] + s[mid]) / 2);
};

注意事项：

- 函数签名中的类型（`number[]`）确保只能传递一个数字数组给函数。但是它可能为空。 - `if (!arr.length) return undefined;` 检查可能为空的数组，这样就没有中位数。 - `[...arr]` 创建传入数组的副本，以确保不会覆盖原始数组。 - `.sort((a, b) => a - b)` 按升序对数字数组进行排序。 - `Math.floor(s.length / 2)` 找到中间元素的索引，如果数组长度为奇数，则找到中间元素的右边一个元素。 - `s.length % 2` 确定数组的长度是否为偶数。 - `(s[mid - 1] + s[mid]) / 2` 对数组的两个中间项取平均值，如果数组的长度是偶数。 - `s[mid]` 是奇数长度数组的中间项。

- David Hansen

---

这个应该得到点赞。绝对是最好的答案。此外，还有 JavaScript 版本（https://www.w3resource.com/javascript-exercises/fundamental/javascript-fundamental-exercise-88.php）。 - Pavol Travnik

Answer 4

上述解决方案 - 先排序再找中间值 - 是可以的，但在大型数据集上速度较慢。先对数据进行排序的复杂度为n x log(n)。

有一种更快的中位数算法，它将数组分成两部分，然后根据枢轴在较大的一组中寻找中位数。这里是一些JavaScript代码，但更详细的解释请参见这里。

// Trying some array
alert(quickselect_median([7,3,5])); // 2300,5,4,0,123,2,76,768,28]));

function quickselect_median(arr) {
   const L = arr.length, halfL = L/2;
   if (L % 2 == 1)
      return quickselect(arr, halfL);
   else
      return 0.5 * (quickselect(arr, halfL - 1) + quickselect(arr, halfL));
}

function quickselect(arr, k) {
   // Select the kth element in arr
   // arr: List of numerics
   // k: Index
   // return: The kth element (in numerical order) of arr
   if (arr.length == 1)
      return arr[0];
   else {
      const pivot = arr[0];
      const lows = arr.filter((e)=>(e<pivot));
      const highs = arr.filter((e)=>(e>pivot));
      const pivots = arr.filter((e)=>(e==pivot));
      if (k < lows.length) // the pivot is too high
         return quickselect(lows, k);
      else if (k < lows.length + pivots.length)// We got lucky and guessed the median
         return pivot;
      else // the pivot is too low
         return quickselect(highs, k - lows.length - pivots.length);
   }
}

细心的读者会注意到以下几点：

1. 我只是将Russel Cohen的Python解决方案转换成JS，所以所有荣誉归于他。
2. 有一些小优化值得做，但是有并行化值得做，而且代码本身更容易在快速的单线程或快速的多线程版本中进行更改。
3. 这是一种平均线性时间算法，还有一种更有效的确定性线性时间版本，请参见Russel的博客文章了解详情，包括性能数据。

2019年9月19日更新：

有评论问是否值得在JavaScript中执行此操作。我在JSPerf中运行了该代码，并得到了有趣的结果。

• 如果数组元素个数为奇数（要查找一个数字），则排序比这个“快速中位数”命题慢20％。

• 如果有偶数个元素，则“快速”算法比较慢40％，因为它需要两次过滤数据，以查找要平均的第k个和第k+1个元素。可以编写一个版本的快速中位数来避免这种情况。

测试使用了相当小的数组（jsperf测试中有29个元素）。随着数组变得越来越大，效果似乎更为明显。更一般的观点是：这表明在JavaScript中值得做这些优化。许多计算都在JS中完成，包括大量数据（考虑仪表板、电子表格、数据可视化），以及资源有限的系统（考虑移动和嵌入式计算）。

- boisvert

---

我正在尝试理解它是否适用于JavaScript。这个快速选择算法似乎是在手动实现快速排序算法。在JavaScript中，排序算法的类型取决于数组的大小和浏览器。当您使用Array.sort()时，后台会选择优化的排序算法。当然，我可能错了，你对此有什么看法？ - Thiago C. S Ventura

我的答案可能更多地反映了我作为一名计算机“教育者”的倾向，而不是从业者 - 我教这个东西，所以这里有一个很棒的教训。像往常一样，上面的算法是否是一个好主意取决于你为什么要这样做。数组有多大？它们很多吗？您将需要在某些时候对数据进行排序，或者需要其他统计信息，例如四分位数等吗？您使用其他库来改变工具选择吗？时间性能对您来说很重要吗？资源对您来说很重要吗？ - boisvert

@ThiagoC.SVentura你的评论促使我测试是否在JSPerf中可见差异。我将结果添加到答案中。 - boisvert

Answer 5

var arr = {  
  max: function(array) {
    return Math.max.apply(null, array);
  },
  
  min: function(array) {
    return Math.min.apply(null, array);
  },
  
  range: function(array) {
    return arr.max(array) - arr.min(array);
  },
  
  midrange: function(array) {
    return arr.range(array) / 2;
  },

  sum: function(array) {
    var num = 0;
    for (var i = 0, l = array.length; i < l; i++) num += array[i];
    return num;
  },
  
  mean: function(array) {
    return arr.sum(array) / array.length;
  },
  
  median: function(array) {
    array.sort(function(a, b) {
      return a - b;
    });
    var mid = array.length / 2;
    return mid % 1 ? array[mid - 0.5] : (array[mid - 1] + array[mid]) / 2;
  },
  
  modes: function(array) {
    if (!array.length) return [];
    var modeMap = {},
      maxCount = 1,
      modes = [array[0]];

    array.forEach(function(val) {
      if (!modeMap[val]) modeMap[val] = 1;
      else modeMap[val]++;

      if (modeMap[val] > maxCount) {
        modes = [val];
        maxCount = modeMap[val];
      }
      else if (modeMap[val] === maxCount) {
        modes.push(val);
        maxCount = modeMap[val];
      }
    });
    return modes;
  },
  
  variance: function(array) {
    var mean = arr.mean(array);
    return arr.mean(array.map(function(num) {
      return Math.pow(num - mean, 2);
    }));
  },
  
  standardDeviation: function(array) {
    return Math.sqrt(arr.variance(array));
  },
  
  meanAbsoluteDeviation: function(array) {
    var mean = arr.mean(array);
    return arr.mean(array.map(function(num) {
      return Math.abs(num - mean);
    }));
  },
  
  zScores: function(array) {
    var mean = arr.mean(array);
    var standardDeviation = arr.standardDeviation(array);
    return array.map(function(num) {
      return (num - mean) / standardDeviation;
    });
  }
};

- Dps

---

谢谢你复制整个库，但这是从哪里来的？ - Déjà vu

再次强调，这个中位数函数在排序时会修改输入的数组。这是需要注意的事项。 - Charles Wood

有人知道这些是否快速吗？它们非常有帮助。 - jboxxx

@jboxxx 是的，它们很快，我已经测试过了。我在LeetCode中使用了一个算法，结果如下： 运行时间：159毫秒，比JavaScript在线提交的Median of Two Sorted Arrays的59.70％更快。 内存使用：47 MB，比JavaScript在线提交的Median of Two Sorted Arrays的71.82％更少。 - Jahanzeb Awan

Answer 6

const median = (arr) => {
  return arr.slice().sort((a, b) => a - b)[Math.floor(arr.length / 2)];
};

- thisismydesign

---

这种方法会给出错误的结果。[1,2,3,4] 的结果是 3，但实际上应该是 2.5。 - undefined

@Mohsen Alyafei 你说的是平均值而不是中位数。 - undefined

不。平均值是5，中位数是2.5。平均值是总数除以2。中位数是中间的数字。如果没有中间的数字，则是两个数字之和除以2。 - undefined

Answer 7

2020 TypeScript答案：

// Calculate Median 
const calculateMedian = (array: Array<number>) => {
  // Check If Data Exists
  if (array.length >= 1) {
    // Sort Array
    array = array.sort((a: number, b: number) => {
      return a - b;
    });

    // Array Length: Even
    if (array.length % 2 === 0) {
      // Average Of Two Middle Numbers
      return (array[(array.length / 2) - 1] + array[array.length / 2]) / 2;
    }
    // Array Length: Odd
    else {
      // Middle Number
      return array[(array.length - 1) / 2];
    }
  }
  else {
    // Error
    console.error('Error: Empty Array (calculateMedian)');
  }
};

- jefelewis

Answer 8

简短而精炼。

Array.prototype.median = function () {
  return this.slice().sort((a, b) => a - b)[Math.floor(this.length / 2)]; 
};

使用

[4, 5, 7, 1, 33].median()

也适用于字符串

["a","a","b","b","c","d","e"].median()

- user1949536

---

[0, 5].median() 的结果为 5。 - Shannon Hochkins

不要改变原型。 - Walter Monecke

const median = (a) => a.slice().sort((a, b) => a - b)[Math.floor(a.length / 2)]; - undefined

Answer 9

arr.sort() 方法会就地对数组元素进行排序，并返回该数组。默认情况下，它按字母顺序排序元素，因此如果数组包含数字，则不会按数值顺序排序。

另一方面，arr.sort((a, b) => a - b) 方法使用回调函数来指定如何对数组进行排序。回调函数比较两个元素 a 和 b，并返回一个负数，如果应该在 b 之前对 a 进行排序，返回正数，如果应该在 a 之前对 b 进行排序，并且如果元素相等则返回零。在这种情况下，回调函数从 a 中减去 b，这将得到一个按升序排列的数字排序顺序。

因此，如果您想按升序对数字数组进行排序，应使用 arr.sort((a, b) => a - b)，而如果要按字母顺序对字符串数组进行排序，则可以使用 arr.sort():

function median(numbers) {
    const sorted = Array.from(numbers).sort((a, b) => a - b);
    const middle = Math.floor(sorted.length / 2);

    if (sorted.length % 2 === 0) {
        return (sorted[middle - 1] + sorted[middle]) / 2;
    }

    return sorted[middle];
}

- Danuja

Answer 10

function median(arr) {
    let n = arr.length;
    let med = Math.floor(n/2);
    if(n % 2 != 0){
       return arr[med];
    } else{
       return (arr[med -1] + arr[med])/ 2.0
    }
 }
 console.log(median[1,2,3,4,5,6]);

- Mochammad Taufiq

---

欢迎来到 Stack Overflow！您的答案可以通过添加更多支持信息来改进。请[编辑]以添加进一步的细节，例如引用或文档，以便他人可以确认您的答案是正确的。您可以在帮助中心中找到有关如何编写良好答案的更多信息。 - Ethan