给定一个整数数组，使用递归找到数组的近似中值

Question

我得到了从 1 个元素到 100_000 个元素的不同长度的 int 数组。我需要找到给定 int 数组的近似中值。例如，

     given array of [4], median is 4 since there is only 1 element

     given array of [4,5], (4+5) / 2.0 = 4.5 is median.

     given array of [4,5,6],

        break array into 3 pieces [4][5][6]

        what is the middle value ? 5 = median.

     given array of [4,5,6,7],

        break array into 3 pieces [4][5,6][7]

        median of [4]   is 4

        median of [5,6] is 5.5

        median of [7]   is 7

          4 vs 5.5 vs 7 

            median of given array [4,5,6,7] is 5.5

使用给定的数组，我应该将数组分成三部分（不创建新数组或修改给定数组）。

将给定数组分成三部分，这是三种可能性

      1. given array's length(6) % 3 = 0 

           (The case when a remainder is 0)

         given array   --> [2,3,5,3,1,4] 

         divide into 3 --> [2,3][5,3][1,4]

                         each pieces are length of n/3. In this particular case(n = 6), 6/3 = 2 = length of each piece.

      2. given array's length(10) % 3 = 1

           (The case when a remainder is 1)

         given array   --> [1,2,-20,-10,7,20,-3,100,6,92]

         divide into 3 --> [1,2,-20][-10,7,20,-3][100,6,92]

                          left and right side piece is length of n/3(10/3).

                          middle piece is n/3(10/3) rounded up

      3. given array's length(8) % 3 = 2

           (Last case when a remainder is 2)

         given array   -->  [1,2,10,7,20,-3,100,6]

         divide into 3 -->  [1,2,10][7,20][-3,100,6]

实现方法 public static double median3(int[] a) {}

这是cs课程的作业，旨在帮助学生练习递归。我感到困惑，因为如果我要使用递归，我不太确定应该从哪里开始。我可以进行从课堂上学到的简单递归，例如斐波那契数列或阶乘数。但是这个问题，我似乎找不到我应用于更简单的递归问题的相同模式......

如果你能给我一些指导并给我一些建议，我将不胜感激。谢谢你。

Answer 1

您可能要处理 3 种情况：对于长度 = 1，您将元素作为该子数组的中位数对于长度 = 2，您将中位数计算为这两个元素的平均值对于长度 >= 3，您根据上述规则拆分数组，然后将相同的方法（即这 3 种情况）应用于第二个（中心）数组。您不需要拆分数组，只需跟踪标记第二个和第三个子数组的第一个元素的索引。例子：让我们从数组开始[1,2,-20,-10,7,20,-3,100,6,92]。它的长度 >= 3 所以你把它分成[1,2,-20][-10,7,20,-3][100,6,92],现在您递归地处理中心数组[-10,7,20,-3]。它的长度仍然 >3，所以你再次分裂并得到[-10[[7,20][-3].“新”中心数组是[7,20]，因为长度为 2，所以您将中位数计算为(7+20)/2.0 = 13.5。