java - 给定一个整数数组,使用递归找到数组的近似中值
问题描述
我得到了从 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课程的作业,旨在帮助学生练习递归。我感到困惑,因为如果我要使用递归,我不太确定应该从哪里开始。我可以进行从课堂上学到的简单递归,例如斐波那契数列或阶乘数。但是这个问题,我似乎找不到我应用于更简单的递归问题的相同模式......
如果你能给我一些指导并给我一些建议,我将不胜感激。谢谢你。
解决方案
您可能要处理 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
。
推荐阅读
- javascript - 每10点后加速JS游戏中的一个对象
- laravel - 获取与所选评论关联的帖子内容(方法帖子不存在)
- amazon-web-services - 尝试从 EC2 实例上的 SQS 队列中读取的身份验证问题 (403),尽管通过 IAM 角色获得了适当的权限
- python - 带有 Docker 的 Python Luigi - 线程/信号问题
- javascript - Html 问题 Iframe,Canvas
- html - 如何创建一个带有倾斜边缘的盒子?
- javascript - 如何显示从服务器返回的 json 对象
- flutter - 如何阻止颤振在错误上运行构建功能
- postgresql - PostgreSQL 会自动创建表的索引吗?
- javascript - 有效的字谜空间复杂度