如何在Java中获得无序列表的中位数

Question

如何计算无序 Java 列表的中位数？

这是我到目前为止编写的代码：

public class MockTest1 {
    /*
     given a random list of integers, find the median e.g. given the list [1, 4, 2, 3, 5] the median is 3 
    */
    
    public static void main(String[] args) {
        List<Integer> array = List.of(1, 3, 4, 5, 2);
        
        System.out.println(getMedian(array));
    }
    
    public static int getMedian(List<Integer> arr) {
        ArrayList<Integer> list = new ArrayList<>(arr);
        
        Collections.sort(list);
        
        double length = (double) list.size();
        
        int med = (int) Math.ceil(length / 2);
        
        return list.get(med - 1);
    }
}

我将列表转换为数组列表以使其可变。

对于我正在使用的示例，即 [1, 3, 4, 5, 2]，我得到的输出为 4 而不是 3，我的共识是，当我调用 get 方法时，列表并未保持排序状态，我该如何解决这个问题？

Answer 1

您的示例中的列表是[1, 2, 3, 4, 5]（已排序），即值 1 在索引 0 处找到，2 在索引 1 处找到，3 在索引 2 处找到，依此类推。列表的大小为 5。中位数可以在索引 5 / 2 == 2（整数除法）处找到。

    public static int getMedian(List<Integer> arr) {
        ArrayList<Integer> list = new ArrayList<>(arr);
        
        Collections.sort(list);
        return list.get(list.size() / 2);
    }

更新

尽管它不是原始问题的一部分，但偶数大小的列表的中位数被定义为列表中间周围两个元素的平均值。假设[1, 2, 3, 4, 5, 6]，那么列表中间没有单个元素。相反，中位数是两个“中间”元素 3 和 4 的平均值，即 (3+4)/2.0。这是一个浮点值，因此返回类型以及计算方式都必须更改：

public static double getMedian(List<Integer> arr) {
    if (arr.isEmpty()) {
        throw new IllegalArgumentException("Can't calculate the median of an empty list");
    }

    ArrayList<Integer> list = new ArrayList<>(arr);
    Collections.sort(list);

    int medianIndex = list.size() / 2;
    double median;
    if (list.size() % 2 == 0) {
        double upper = list.get(medianIndex).doubleValue();
        double lower = list.get(medianIndex - 1).doubleValue();
        median = (lower + upper) / 2.0;
    } else {
        median = list.get(medianIndex).doubleValue();
    }
    return median;
}