language-agnostic - 在数字集合中找到最接近的匹配项

Question

所以我今天被问到在一个集合中找到接近匹配的最佳方法是什么。

例如，你有一个这样的数组：

1, 3, 8, 10, 13, ...

最接近4的数是多少？

集合是数字的，无序的，可以是任何东西。与要匹配的数字相同。

让我们看看我们可以从选择的各种语言中得出什么。

Answer 1

J 中的 11 个字节：

C=:0{]/:|@-

例子：

>> a =: 1 3 8 10 13
>> 4 C a
3
>> 11 C a
10
>> 12 C a
13

我对外行的细分：

0{         First element of
]          the right argument
/:         sorted by
|          absolute value 
@          of
-          subtraction

Answer 2

较短的 Python：41 个字符

f=lambda a,l:min(l,key=lambda x:abs(x-a))

Answer 3

我在 python 中的尝试：

def closest(target, collection) :
    return min((abs(target - i), i) for i in collection)[1]

Answer 4

时髦的 28B

f={a,n->a.min{(it-n).abs()}}

Answer 5

一些 C# Linq 的……太多的方法来做到这一点！

decimal[] nums = { 1, 3, 8, 12 };
decimal target = 4;

var close1 = (from n in nums orderby Math.Abs(n-target) select n).First();
var close2 = nums.OrderBy(n => Math.Abs(n - target)).First();

Console.WriteLine("{0} and {1}", close1, close2);

如果您改用列表，则可以使用更多方法，因为普通的 ol 数组没有 .Sort()

Answer 6

假设值从名为 T 的表中开始，列名为 N，并且我们正在寻找值 4，那么在 Oracle SQL 中它需要 59 个字符：

select*from(select*from t order by abs(n-4))where rownum=1

我使用 select * 来减少空格要求。

Answer 7

PostgreSQL：

select n from tbl order by abs(4 - n) limit 1

在两条记录共享相同值的“abs(4 - id)”的情况下，输出将是不确定的并且可能不是常数。为了解决这个问题，我建议像未经测试的猜测：

select n from tbl order by abs(4 - n) + 0.5 * 4 > n limit 1;

此解决方案提供 O(N log N) 量级的性能，其中 O(log N) 是可能的，例如：https ://stackoverflow.com/a/8900318/1153319

Answer 8

因为我实际上需要这样做，所以这是我的 PHP

$match = 33;

$set = array(1,2,3,5,8,13,21,34,55,89,144,233,377,610);

foreach ($set as $fib)
    {
        $diff[$fib] = (int) abs($match - $fib);
    }
$fibs = array_flip($diff);
$closest = $fibs[min($diff)];

echo $closest;

Answer 9

像 Python 这样的 Ruby 有一个用于 Enumerable 的 min 方法，因此您不需要进行排序。

def c(value, t_array)
  t_array.min{|a,b|  (value-a).abs <=> (value-b).abs }
end

ar = [1, 3, 8, 10, 13]
t = 4
c(t, ar) = 3

Answer 10

语言：C，字符数：79

c(int v,int*a,int A){int n=*a;for(;--A;++a)n=abs(v-*a)<abs(v-n)?*a:n;return n;}

签名：

int closest(int value, int *array, int array_size);

用法：

main()
{
    int a[5] = {1, 3, 8, 10, 13};
    printf("%d\n", c(4, a, 5));
}

Answer 11

Scala（62 个字符），基于 J 和 Ruby 解决方案的思想：

def c(l:List[Int],n:Int)=l.sort((a,b)=>(a-n).abs<(b-n).abs)(0)

用法：

println(c(List(1,3,8,10,13),4))

Answer 12

上面的代码不适用于浮点数。
所以这是我修改后的 php 代码。

function find_closest($match, $set=array()) {
    foreach ($set as $fib) {  
        $diff[$fib] = abs($match - $fib);  
    }  
    return array_search(min($diff), $diff);  
}

$set = array('2.3', '3.4', '3.56', '4.05', '5.5', '5.67');  
echo find_closest(3.85, $set); //return 4.05  

Answer 13

PostgreSQL：

这在 FreeNode 上由 RhodiumToad 指出，并且性能约为 O(log N)。，比此处的其他 PostgreSQL 答案要好得多。

select * from ((select * from tbl where id <= 4
order by id desc limit 1) union
(select * from tbl where id >= 4
order by id limit 1)) s order by abs(4 - id) limit 1;

为了更好地处理 id 存在的情况，两个条件都应该是“或等于”。这也适用于两条记录共享相同值的“abs(4 - id)”然后其他 PostgreSQL 在这里回答的情况。

Answer 14

Python by 我和https://stackoverflow.com/users/29253/igorgue基于此处的其他一些答案。只有 34 个字符：

min([(abs(t-x), x) for x in a])[1]

Answer 15

已编辑 = 在 for 循环中

int Closest(int val, int[] arr)
{
    int index = 0;
    for (int i = 0; i < arr.Length; i++)
        if (Math.Abs(arr[i] - val) < Math.Abs(arr[index] - val))
            index = i;
    return arr[index];
}

Answer 16

Haskell 条目（已测试）：

import Data.List

near4 = head . sortBy (\n1 n2 -> abs (n1-4) `compare` abs (n2-4))

通过将接近 4 的数字放在前面附近来对列表进行排序。 head取第一个元素（最接近 4）。

Answer 17

红宝石

def c(r,t)
r.sort{|a,b|(a-t).abs<=>(b-t).abs}[0]
end

不是最有效的方法，但很短。

Answer 18

只返回一个数字：

var arr = new int[] { 1, 3, 8, 10, 13 };
int numToMatch = 4;
Console.WriteLine("{0}", 
     arr.Select(n => new{n, diff = Math.Abs(numToMatch - n) }).OrderBy(x => x.diff).ElementAt(0).n);

Answer 19

只返回一个数字：

var arr = new int[] { 1, 3, 8, 10, 13 };
int numToMatch = 4;

Console.WriteLine("{0}", 
   arr.OrderBy(n => Math.Abs(numToMatch - n)).ElementAt(0));

Answer 20

Perl -- 66 个字符：

perl -e 'for(qw/1 3 8 10 13/){$d=($_-4)**2; $c=$_ if not $x or $d<$x;$x=$d;}print $c;'

Answer 21

这是另一个 Haskell 答案：

import Control.Arrow
near4 = snd . minimum . map (abs . subtract 4 &&& id)

Answer 22

Haskell，60 个字符 -

f a=head.Data.List.sortBy(compare`Data.Function.on`abs.(a-))

Answer 23

Kdb+ , 23B:

C:{x first iasc abs x-}

用法：

q)a:10?20
q)a
12 8 10 1 9 11 5 6 1 5

q)C[a]4
5

Answer 24

在 Java 中使用可导航的地图

NavigableMap <Integer, Integer>navMap = new ConcurrentSkipListMap<Integer, Integer>();  

navMap.put(15000, 3);  
navMap.put(8000, 1);  
navMap.put(12000, 2);  

System.out.println("Entry <= 12500:"+navMap.floorEntry(12500).getKey());  
System.out.println("Entry <= 12000:"+navMap.floorEntry(12000).getKey());  
System.out.println("Entry > 12000:"+navMap.higherEntry(12000).getKey()); 

Answer 25

Python，不确定如何格式化代码，也不确定代码是否会按原样运行，但它的逻辑应该可以工作，而且无论如何可能有内置函数......

list = [1,4,10,20]
num = 7
for lower in list:
         if lower <= num:
           lowest = lower #closest lowest number

for higher in list:
     if higher >= num:
           highest = higher #closest highest number

if highest - num > num - lowest: # compares the differences
    closer_num = highest
else:
    closer_num = lowest

Answer 26

int numberToMatch = 4;

var closestMatches = new List<int>();
closestMatches.Add(arr[0]); // closest tentatively

int closestDifference = Math.Abs(numberToMatch - arr[0]);


for(int i = 1; i < arr.Length; i++)
{
    int difference = Math.Abs(numberToMatch - arr[i]);
    if (difference < closestDifference)
    {
        closestMatches.Clear();
        closestMatches.Add(arr[i]);
        closestDifference = difference;
    }
    else if (difference == closestDifference)
    {       
        closestMatches.Add(arr[i]);
    }
}


Console.WriteLine("Closest Matches");
foreach(int x in closestMatches) Console.WriteLine("{0}", x);

Answer 27

你们中的一些人似乎没有读到这个列表unordered（尽管我可以理解你的困惑）。在 Java 中：

public int closest(int needle, int haystack[]) { // yes i've been doing PHP lately
  assert haystack != null;
  assert haystack.length; > 0;
  int ret = haystack[0];
  int diff = Math.abs(ret - needle);
  for (int i=1; i<haystack.length; i++) {
    if (ret != haystack[i]) {
      int newdiff = Math.abs(haystack[i] - needle);
      if (newdiff < diff) {
        ret = haystack[i];
        diff = newdiff;
      }
    }
  }
  return ret;
}

不完全简洁，但嘿它的Java。

Answer 28

Common Lisp使用迭代库。

(defun closest-match (list n)
     (iter (for i in list)
            (finding i minimizing (abs (- i n)))

Answer 29

F#中的41 个字符：

let C x = Seq.min_by (fun n -> abs(n-x))

如在

#light

let l = [1;3;8;10;13]

let C x = Seq.min_by (fun n -> abs(n-x))

printfn "%d" (C 4 l)   // 3 
printfn "%d" (C 11 l)  // 10
printfn "%d" (C 12 l)  // 13

Answer 30

红宝石。一通。很好地处理负数。也许不是很短，但肯定很漂亮。

class Array
  def closest int
    diff = int-self[0]; best = self[0]
    each {|i|
      if (int-i).abs < diff.abs
        best = i; diff = int-i
      end
    }
    best
  end
end

puts [1,3,8,10,13].closest 4

Answer 31

Excel VBA - 查找 Excel 范围的索引或最接近目标值的值

给定一个现有的 Excel 范围，rangeOfValues：

1. 使用 Application.Match 查找 Range 中最接近匹配值的索引（注意 Match 方法返回一个 Double）

   Dim iMatch as Double 
   iMatch = Application.Match(valueToMatch, rangeOfValues)
   

2. 使用 VLOOKUP/HLOOKUP 找到最接近目标值的范围值

   Dim closest as Variant
   closest = VLOOKUP(valueToMatch, rangeOfValues)
   

如果需要完全匹配：

Dim exactM as Variant
exactM = VLOOKUP(valueToMatch, rangeOfValues, False)

Answer 32

另一个 PHP 答案：

function closestMatch($int, $in) {
    $diffs = array();
    foreach ($in as $i)
        $diffs[abs($int - $i)] = $i;
    ksort($diffs);
    foreach ($diffs as $i) return $i;
}

Answer 33

Python + 麻木

import numpy as np
f = lambda lst, target: lst[np.argmin(np.abs(np.array(lst) - target))]

例子：

>>> f([1,2,5,3,10],9)
10