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

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. 对于长度 = 1，您将元素作为该子数组的中位数

2. 对于长度 = 2，您将中位数计算为这两个元素的平均值

3. 对于长度 >= 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。