如何在 Java 中计算数组的中位数

Java 3月前 119

在计算机科学中，数组是一种常见的数据结构，它能够存储和操作多个相同类型的元素。计算数组的中位数是一个常见的问题，特别是在统计学和数学领域。在Java编程语言中，我们可以使用不同的方法来计算数组的中位数。

一、简单方法

首先，我们可以使用最简单的方法来计算数组的中位数，即对数组进行排序并找到中间位置的元素（如果数组的大小是奇数）或中间两个元素的平均值（如果数组的大小是偶数）。以下是一个示例代码：

import java.util.Arrays;

public class MedianCalculator {
   public static double calculateMedian(int[] nums) {
      Arrays.sort(nums);
      int size = nums.length;
      if (size % 2 == 0) {
         return (nums[size/2 - 1] + nums[size/2]) / 2.0;
      } else {
         return nums[size/2] / 1.0;
      }
   }
   
   public static void main(String[] args) {
      int[] array = {5, 2, 9, 1, 7, 6, 3};
      double median = calculateMedian(array);
      System.out.println("中位数是: " + median);
   }
}

在上面的示例代码中，我们首先使用Arrays.sort(nums)函数对数组进行排序。然后，我们计算数组的大小，并使用条件语句判断数组的大小是奇数还是偶数。最后，我们返回中位数作为函数的计算结果。

在上述示例中，我们使用整数数组int[] array = {5, 2, 9, 1, 7, 6, 3}作为输入。程序打印输出的结果是：

中位数是: 5.0

因为数组的大小是奇数，中位数为5。

二、优化方法

上述方法虽然简单易懂，但是需要额外的空间和时间来进行排序操作。在某些情况下，我们可能需要更高效的方法来计算数组的中位数。下面我们介绍一种不需要排序的优化方法。
以下是示例代码：

import java.util.PriorityQueue;

public class MedianCalculator {
   public static double calculateMedian(int[] nums) {
      PriorityQueue<Integer> minHeap = new PriorityQueue<>();
      PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
      
      for (int num : nums) {
         maxHeap.offer(num);
         minHeap.offer(maxHeap.poll());
         if (maxHeap.size() < minHeap.size()) {
            maxHeap.offer(minHeap.poll());
         }
      }
      
      if (maxHeap.size() == minHeap.size()) {
         return (maxHeap.peek() + minHeap.peek()) / 2.0;
      } else {
         return maxHeap.peek() / 1.0;
      }
   }
   
   public static void main(String[] args) {
      int[] array = {5, 2, 9, 1, 7, 6, 3};
      double median = calculateMedian(array);
      System.out.println("中位数是: " + median);
   }
}

在上述示例代码中，我们使用两个优先级队列（堆）来存储数组的元素。一个最小堆（存储较大的一半元素），一个最大堆（存储较小的一半元素）。我们使用循环遍历数组，将元素分别插入到两个堆中。同时，我们需要保持两个堆的大小平衡。最后，根据两个堆的大小，我们可以找到中位数。

在上述示例中，我们同样使用整数数组int[] array = {5, 2, 9, 1, 7, 6, 3}作为输入。程序打印输出的结果是：

中位数是: 5.0

注意事项：

在使用第一种简单方法时，由于涉及到对数组进行排序操作，因此时间复杂度为O(nlog(n))。在数据量大的情况下，可能会影响程序的性能。
在使用第二种优化方法时，我们使用了两个堆来存储数组的元素。此方法的时间复杂度仅为O(nlog(n))，并且可以在常数时间内查询中位数。但是，需要额外的空间来存储堆的元素。
在计算数组的中位数时，需要考虑数组的大小是奇数还是偶数，并根据情况返回不同的结果。
在编写代码时，应该考虑异常情况，例如空数组或长度为0的数组，以避免程序出错。