查找一个不接近 NSMutableArray 中任何整数的整数

Question

我有一个 NSMutableArray，它有 5 个值最初设置为零。它包含屏幕上元素的 x 坐标，每 1/60 秒更新一次。每个项目的位置都在不断变化。屏幕上最多有 5 个项目，任何时候最少有 1 个。

数组中的每个项目的范围为 0 - 480（iPhone 屏幕的高度）。给定时间的示例数组为：

{123,450,0,0,0}

然后可能会更改为：

{150,320,90,0,0}

我需要一种快速查找不靠近数组中任何位置的位置的方法。这可以是不在每个值周围的设定范围内的位置（例如，该值不在数组中任何项目的 50 个范围内），也可以是其两侧距离最远的位置。

显然，如果不可能在一定范围内找到位置，则应该选择最佳解决方案。

当新项目添加到屏幕上时，它需要很快，因此选择新位置的任何延迟都会减慢游戏的速度 - 因此 while 循环并不可取。

希望 Objective-C 中有一个简单的数学方法可以解决这个问题。我真的很困惑应该如何实现这一目标。任何帮助都非常感谢。

Answer 1

让我稍微改一下这个问题。你有点p1,p2,p3,p4,p5，

0 <= p_i <= 480

你想找到一个点x，使得

0 <= x <= 480

函数最大化

min_{x} ( |p1-x| + |p2-x| + |p3-x| + |p4-x| + |p5-x| )

如果这是你的目标（而且它不是我不清楚它是或应该是），那么您可以通过检查以下哪个潜在 x 值最大化距离来解决此问题：

0 , p1/2 , p1 + (p2-p1)/2 , p2 + (p3-p2)/2 , ... , p5 + (480-p5)/2

假设 0 <= p1 < ;= p2 <= p3 <= p4 <= p5 <= 480。您应该选择差异项中较大的答案。

例如，

{123,450,0,0,0}

答案是123 + (450-123)/2。

要

{150,320,90,0,0} 

答案是 150 + (320-150)/2

在 Objective-C 中进行编码，您需要一个函数来返回最大条目的索引一个数组。将输入设为p1,p2,...,p5。将它们按升序排列，在左侧附加 0，在右侧附加 480。然后创建一个长度减一的新数组，给出连续的差异，例如 {p1-p0, p2-p1, ..., p6-p5} 其中 p0 = 0和p6 = 480。最后，获取这个新数组的最大值的索引，将其称为i，并返回最佳位置p_i + (p(i+1)-p_i)/2 。

示例：

输入：{150,320,90,0,0}

重新排列为{0 , 0 , 0 , 90 , 150 , 320 , 480}

索引处的差异数组 {0 , 0 , 90 , 60 , 170 , 160}

最大值4

答案是 150 + (320-150)/2

Answer 2

我不认为有一个 Objective-C 对象可以为你做这件事——你实际上必须做一些编程。

我想到的第一个想法是某种树，但简单的 B 树或其他什么都不是。也许是一棵笛卡尔树，但我现在还不知道如何应用它。

或者你可以直接暴力破解——将值按顺序排列并扫描列表以找到最大的差距。