Вычисление медианы списка — распространенная задача в анализе данных и статистике. В Java существует несколько подходов к поиску медианы. В этой статье блога мы рассмотрим семь различных методов с примерами кода для вычисления медианы списка. Независимо от того, новичок вы или опытный Java-разработчик, эта статья предоставит вам полный обзор различных методов поиска медианы.

Методы:

1. Сортировка и поиск среднего элемента:

   • Отсортируйте список по возрастанию.
   • Если размер списка нечетный, медианой является средний элемент.
   • Если размер списка четный, медиана представляет собой среднее значение двух средних элементов.

   import java.util.Collections;
   import java.util.List;
   public class MedianCalculator {
      public static double findMedian(List<Integer> list) {
          Collections.sort(list);
          int size = list.size();
          int middle = size / 2;
          if (size % 2 == 0) {
              return (list.get(middle - 1) + list.get(middle)) / 2.0;
          } else {
              return list.get(middle);
          }
      }
   }

2. Использование Apache Commons Math:

   • Библиотека Apache Commons Math предоставляет класс Median, который вычисляет медиану массива или списка.

   import org.apache.commons.math3.stat.descriptive.rank.Median;
   import java.util.List;
   public class MedianCalculator {
      public static double findMedian(List<Integer> list) {
          Median median = new Median();
          return median.evaluate(list.stream().mapToDouble(Integer::doubleValue).toArray());
      }
   }

3. Использование потоков Java:

   • В Java 8 появился API Stream, который можно использовать для поиска медианы с помощью краткого фрагмента кода.

   import java.util.List;
   public class MedianCalculator {
      public static double findMedian(List<Integer> list) {
          int size = list.size();
          return list.stream()
                     .sorted()
                     .skip((size - 1) / 2)
                     .limit(2 - size % 2)
                     .mapToInt(Integer::intValue)
                     .average()
                     .orElse(Double.NaN);
      }
   }

4. Алгоритм быстрого выбора:

   • Быстрый выбор – эффективный алгоритм поиска k-го элемента в неупорядоченном списке. Его можно использовать для нахождения медианы, выбрав средний элемент.

   import java.util.List;
   import java.util.Random;
   public class MedianCalculator {
      private static Random random = new Random();
      public static double findMedian(List<Integer> list) {
          int size = list.size();
          int k = size / 2;
          return quickSelect(list, 0, size - 1, k);
      }
      private static double quickSelect(List<Integer> list, int left, int right, int k) {
          if (left == right) {
              return list.get(left);
          }
          int pivotIndex = partition(list, left, right);
          if (k == pivotIndex) {
              return list.get(k);
          } else if (k < pivotIndex) {
              return quickSelect(list, left, pivotIndex - 1, k);
          } else {
              return quickSelect(list, pivotIndex + 1, right, k);
          }
      }
      private static int partition(List<Integer> list, int left, int right) {
          int pivotIndex = left + random.nextInt(right - left + 1);
          int pivotValue = list.get(pivotIndex);
          int i = left;
          Collections.swap(list, pivotIndex, right);
          for (int j = left; j < right; j++) {
              if (list.get(j) < pivotValue) {
                  Collections.swap(list, i, j);
                  i++;
              }
          }
          Collections.swap(list, i, right);
          return i;
      }
   }

5. Использование TreeSet:

   • TreeSet — это красно-черная древовидная реализация интерфейса SortedSet. Он автоматически сохраняет элементы в отсортированном порядке, что упрощает поиск медианы.

   import java.util.List;
   import java.util.TreeSet;
   public class MedianCalculator {
      public static double findMedian(List<Integer> list) {
          TreeSet<Integer> sortedSet = new TreeSet<>(list);
          int size = sortedSet.size();
          int middle = size / 2;
          if (size % 2 == 0) {
              return (sortedSet.ceiling(middle) + sortedSet.floor(middle)) / 2.0;
          } else {
              return sortedSet.ceiling(middle);
          }
      }
   }

6. Использование Collections.binarySearch:

   • Если список уже отсортирован, для эффективного нахождения медианы можно использовать двоичный поиск“`java
     import java.util.Collections;
     import java.util.List;
     public class MedianCalculator {
     public static double findMedian(Listlist) {
     Collections.sort(list);
     int size = list.size();
     int middle = size / 2;
     if (size % 2 == 0) {
     return (list.get(middle – 1) + list.get(middle)) / 2.0;
     } else {
     return list.get (средний);
     }
     }
     }

7. Использование Apache Commons Math:

   • Библиотека Apache Commons Math предоставляет класс Median, который вычисляет медиану массива или списка.

   import org.apache.commons.math3.stat.descriptive.rank.Median;
   import java.util.List;
   public class MedianCalculator {
       public static double findMedian(List<Integer> list) {
           Median median = new Median();
           return median.evaluate(list.stream().mapToDouble(Integer::doubleValue).toArray());
       }
   }

В этой статье мы рассмотрели семь различных методов расчета медианы списка в Java. Каждый метод предлагает свой подход к поиску медианы, что позволяет вам выбрать тот, который лучше всего соответствует вашим потребностям. Независимо от того, предпочитаете ли вы сортировку, использование внешних библиотек или встроенные функции Java, эти методы предоставляют вам множество возможностей. Поняв эти методы, вы сможете эффективно выполнять медианные вычисления в своих проектах Java.