在随机集合中找到最接近的数字

Question

假设我有一组10个随机数字，这些数字的范围在0到100之间。

一个操作员还给了我一个0到100之间的随机数字。然后我需要找出这个数字集合中距离操作员给我的数字最近的数字。

例子

数字集合 = {1,10,34,39,69,89,94,96,98,100}

操作员给的数字 = 45

返回结果 = 39

如何将此转换为代码？（JavaScript或其他语言）

- Andy Jacobs

Answer 1

如果集合有序，可以通过二分查找找到最接近的值（或两个值）。然后通过...减法来区分哪一个是最接近的？

如果集合没有排序，只需迭代整个集合（对其进行排序需要多次遍历），对于每个成员，检查差异是否小于迄今为止最小的差异，并且如果是，则将其记录为新的最小差异，并将该数字作为新的候选答案。

  public int FindClosest(int targetVal, int[] set)
  {
      int dif = 100, cand = 0;
      foreach(int x in set)
          if (Math.Abs(x-targetVal) < dif)
          {
              dif = Math.Abs(x-targetVal);
              cand = x;
          }
      return cand;
  }

- Charles Bretana

---

如果经常执行这样的搜索，对数组进行排序可能会很有用，否则就不需要。 - SebastianK

如果集合是无序的，那么对数组进行排序是否比通过无序列表进行一次遍历更耗时？ - Charles Bretana

@Charles Bretana：关键在于SebastianK说的是“如果这样的搜索经常进行”。假设我们有n个数字，我们要在其中找到最接近的数字，并且我们要重复这个过程m次。如果我们不排序，时间复杂度为O(mn)。如果我们进行排序，则复杂度为O(n log n + m log n)，因为排序是O(n log n)，二分搜索是O(log n)。如果m >> n，则时间复杂度为O(m log n)，优于O(mn)。 - jason

@Jason，假设已经对数组进行了排序以便于下一次搜索，你是正确的，SebastianK也是正确的。 - Charles Bretana

Answer 2

• 给定一个名为input的数组，请创建一个与之同样大小的新数组
• 这个新数组的每个元素都是Math.abs(input[i] - operatorNumber)
• 选择最小元素的索引（我们称其为k）
• 答案是input[k]

NB

• 不需要排序
• 你可以不用额外的数组来达成目标

JavaScript中的代码实现示例

function closestTo(number, set) {
    var closest = set[0];
    var prev = Math.abs(set[0] - number);

    for (var i = 1; i < set.length; i++) {
        var diff = Math.abs(set[i] - number);

        if (diff < prev) {
            prev = diff;
            closest = set[i];
        }
    }

    return closest;
}

- dfa

Answer 3

有人在这个问题上打了Mathematica的标签，所以这里提供一个Mathematica的答案：

set = {1,10,34,39,69,89,94,96,98,100};

opno = 45;

set[[Flatten[
  Position[set - opno, i_ /; Abs[i] == Min[Abs[set - opno]]]]]]

当集合中有多个元素与运算符号数字等距离时，它就能正常工作。

- High Performance Mark

---

不错的解决方案！（同时我删除了Mathematica标签，因为我认为这可能不是有意的。如果我猜错了，原作者可以重新添加它。） - dreeves

Answer 4

这样怎么样：

1）将集合放入二叉树中。
2）将运算符号插入到树中。
3）返回运算符的父节点。

- tinkertime

Answer 5

1. 对集合进行排序
2. 对输入进行二分查找
3. 如果你最终处于两个元素之间，请检查它们的差异，并返回差异最小的那个。

- GSto

---

对集合进行排序需要O(n log n)的时间复杂度。我认为有一种O(n)的解决方案。 - jpbochi

排序的时间复杂度为O(n log n)，只需一次。如果您只需要检查一次，则每个值的O(n)检查更好。如果您需要经常检查，则一次性的O(n log n)，然后每次检查的O(log n)要好得多。 - Vincent McNabb

Answer 6

Python示例：

#!/usr/bin/env python
import random
from operator import itemgetter

sample = random.sample(range(100), 10)
pivot = random.randint(0, 100)

print 'sample: ', sample
print 'pivot:', pivot
print 'closest:', sample[
    sorted(
        map(lambda i, e: (i, abs(e - pivot)), range(10), sample), 
        key=itemgetter(1)
    )[1][0]]

# sample:  [61, 2, 3, 85, 15, 18, 19, 8, 66, 4]
# pivot: 51
# closest: 66

- miku