java - 从频率表中获取中位数(计数排序)

Question

我无法理解 getMedian 方法背后的逻辑。中位数究竟是如何计算的，元素个数和元素总和之间有什么联系？感谢有人可以解释它的逻辑。

  public static void main(String[] args) {
            Random r = new Random();
            int[] ar = r.ints(0, 100).limit(9).toArray();
            int k = ar.length;
            int[] count = getCounts(ar);
            double median = getMedian(count, k);
            System.out.println(median);
        }

        private static int[] getCounts(int[] ar) {
            int[] count = new int[100];
            for (int i = 0; i < ar.length; i++) {
                count[ar[i]]++;
            }
            return count;
        }

        private static double getMedian(int[] count, int d) {
            int sum = 0;
            for (int i = 0; i < count.length; i++) {
                sum += count[i];
                if (2 * sum < d)
                    continue;
                else if (2 * sum == d)
                    return (2 * i + 1) / 2.0;
                else
                    return i * 1.0;
            }
            return -1.0;
        }

Answer 1

有关系是因为是频率表。你的想法不同，但让我举个例子。

1 1 1 3 3 4 4 4 5 5 5 5 如果这是数组，那么频率表将是:-

1 3 4 5
- - - -
3 2 3 4

所以这是 median .所以现在我添加每个元素计数并问我们一个问题，中位数在哪里？或者 indexm 在哪里，如果我认为我将覆盖中间元素？

现在我正在检查 sum > d/2 那么它就完成了。我们找到了 median.else 如果它小于那么我仍然必须遍历其他元素才能到达数组的中间。如果它是 sum==d/2 那么我们已经找到它但是我们必须发送正确的位置。我们只需发送位于中下部的那个(发生在 1,1,1,1 的情况下)。

遍历

1 1 1 3 3 4 4 4 5 5 5 5

现在我检查我是否遍历了我所在位置的所有 1 集？我涵盖了 3 个元素。但这不是总数的一半(6)。

现在添加 3 的个数。 5. 这也不是。

现在我添加了 4 的个数，所以我涵盖了 8 个元素。所以我覆盖了一半以上的元素。所以中位数就在这里。

更详细的解释:

要求您找出 10 个整数数组的中位数。

[1 2 3 4 5 6 7 8 9]

那么median在位置floor(9/2)=4的元素中，也就是5对吧？

[1 1 2 2 3 3 4 4 5]

位置floor(9/2)=4的中位元素在哪里，也就是3，对吧？

所以现在想想，

 1  2 3 4 5
 2  2 2 2 1

现在您将尝试从头开始在此处找到第 (9/2) 个元素。这就是为什么您需要找到频率和所有频率的总和。

希望你明白了吗？

正确的算法

你需要做的是:-

N = number of elements.
F[] = frequency array
so if N is odd
  find the element at floor(N/2)-th place and median is that element.
else
  find the element at floor((N-1)/2) and floor(N/2) th position and return their average.

Finding the element is simple:
Find( F[], p) // find the element at position p
{
  p=p+1
  for i in [0..|F|]
    cumulative+=F[i]
    if cumulative == p
      return this element.
    else cumulative >p
      return this element  
}