当前位置： 文江博客话题详情

在数字集合中查找最接近的匹配

发布于 2024-07-11 12:08:56 字数 204 浏览 7 评论 0原文

所以今天有人问我在集合中查找结束匹配的最佳方法是什么。

例如，您有一个如下所示的数组：

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

哪个数字最接近 4？

集合是数字的、无序的并且可以是任何东西。 与要匹配的号码相同。

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

原文

So I got asked today what was the best way to find the closes match within a collection.

For example, you've got an array like this:

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

What number is closest to 4?

Collection is numerical, unordered and can be anything. Same with the number to match.

Lets see what we can come up with, from the various languages of choice.

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（30）

蓝戈者 2024-07-18 12:08:56

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

11 bytes in J:

C=:0{]/:|@-

Examples:

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

my breakdown for the layman:

0{         First element of
]          the right argument
/:         sorted by
|          absolute value 
@          of
-          subtraction
回复 原文
§普罗旺斯的薰衣草 2024-07-18 12:08:56

更短的 Python：41 个字符

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

Shorter Python: 41 chars

f=lambda a,l:min(l,key=lambda x:abs(x-a))
回复 原文
千里故人稀 2024-07-18 12:08:56

我在Python中的尝试：

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

My attempt in python:

def closest(target, collection) :
    return min((abs(target - i), i) for i in collection)[1]
回复 原文
夜吻♂芭芘 2024-07-18 12:08:56

Groovy 28B

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

Groovy 28B

f={a,n->a.min{(it-n).abs()}}
回复 原文
蓝眼睛不忧郁 2024-07-18 12:08:56

一些 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()

Some C# Linq ones... too many ways to do this!

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);

Even more ways if you use a list instead, since plain ol arrays have no .Sort()

回复 原文
守不住的情 2024-07-18 12:08:56

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

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

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

Assuming that the values start in a table called T with a column called N, and we are looking for the value 4 then in Oracle SQL it takes 59 characters:

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

I've used select * to reduce the whitespace requirements.

回复 原文
短暂陪伴 2024-07-18 12:08:56

因为我实际上需要这样做，这是我的 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;

Because I actually needed to do this, here is my 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;
回复 原文
Oo萌小芽oO 2024-07-18 12:08:56

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

PostgreSQL:

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

In the case where two records share the same value for "abs(4 - id)" the output would be in-determinant and perhaps not a constant. To fix that I suggest something like the untested guess:

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

This solution provides performance on the order of O(N log N), where O(log N) is possible for example: https://stackoverflow.com/a/8900318/1153319

回复 原文
三生殊途 2024-07-18 12:08:56

像 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

Ruby like Python has a min method for Enumerable so you don't need to do a sort.

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
回复 原文
徒留西风 2024-07-18 12:08:56

语言：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));
}

Language: C, Char count: 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;}

Signature:

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

Usage:

main()
{
    int a[5] = {1, 3, 8, 10, 13};
    printf("%d\n", c(4, a, 5));
}
回复 原文
红衣飘飘貌似仙 2024-07-18 12:08:56

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))

Scala (62 chars), based on the idea of the J and Ruby solutions:

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

Usage:

println(c(List(1,3,8,10,13),4))
回复 原文
最佳男配角 2024-07-18 12:08:56

PostgreSQL：

这是由 RhodiumToad 在 FreeNode 上指出的，其性能约为 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 在这里回答。

PostgreSQL:

This was pointed out by RhodiumToad on FreeNode and has performance on the order of O(log N)., much better then the other PostgreSQL answer here.

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;

Both of the conditionals should be "or equal to" for much better handling of the id exists case. This also has handling in the case where two records share the same value for "abs(4 - id)" then that other PostgreSQL answer here.

回复 原文
奶茶白久 2024-07-18 12:08:56

上面的代码不适用于浮点数。
这是我修改后的 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

The above code doesn't works for floating numbers.
So here's my revised php code for that.

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
回复 原文
君勿笑 2024-07-18 12:08:56

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

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

Python by me and https://stackoverflow.com/users/29253/igorgue based on some of the other answers here. Only 34 characters:

min([(abs(t-x), x) for x in a])[1]
回复 原文
奢欲 2024-07-18 12:08:56

Haskell 条目（已测试）：

import Data.List

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

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

Haskell entry (tested):

import Data.List

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

Sorts the list by putting numbers closer to 4 near the the front. head takes the first element (closest to 4).

回复 原文
软糖 2024-07-18 12:08:56

Ruby

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

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

Ruby

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

Not the most efficient method, but pretty short.

回复 原文
喜你已久 2024-07-18 12:08:56

仅返回一个数字：

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

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

returns only one number:

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

Console.WriteLine("{0}", 
   arr.OrderBy(n => Math.Abs(numToMatch - n)).ElementAt(0));
回复 原文
相对绾红妆 2024-07-18 12:08:56

仅返回一个数字：

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);

returns only one number:

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);
回复 原文
逐鹿 2024-07-18 12:08:56

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;'

Perl -- 66 chars:

perl -e 'for(qw/1 3 8 10 13/){$d=($_-4)**2; $c=$_ if not $x or $d<$x;$x=$d;}print $c;'
回复 原文
暗喜 2024-07-18 12:08:56

已编辑 = 在 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];
}

EDITED = in the for loop

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];
}
回复 原文
☆獨立☆ 2024-07-18 12:08:56

这是另一个 Haskell 答案：

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

Here's another Haskell answer:

import Control.Arrow
near4 = snd . minimum . map (abs . subtract 4 &&& id)
回复 原文
故事灯 2024-07-18 12:08:56

Haskell，60 个字符 -

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

Haskell, 60 characters -

f a=head.Data.List.sortBy(compare`Data.Function.on`abs.(a-))
回复 原文
勿忘初心 2024-07-18 12:08:56

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

Kdb+, 23B:

C:{x first iasc abs x-}

Usage:

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

q)C[a]4
5
回复 原文
如此安好 2024-07-18 12:08:56

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

Python, not sure how to format code, and not sure if code will run as is, but it's logic should work, and there maybe builtins that do it anyways...

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
回复 原文
深居我梦 2024-07-18 12:08:56

在 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());

In Java Use a Navigable Map

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());
回复 原文
一个人的旅程 2024-07-18 12:08:56
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);

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);
回复 原文
深白境迁sunset 2024-07-18 12:08:56

你们中的一些人似乎没有意识到该列表是无序的（尽管通过示例，我可以理解您的困惑）。 在 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。

Some of you don't seem to be reading that the list is unordered (although with the example as it is I can understand your confusion). In 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;
}

Not exactly terse but hey its Java.

回复 原文
谁的年少不轻狂 2024-07-18 12:08:56

Common Lisp 使用迭代库。

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

Common Lisp using iterate library.

(defun closest-match (list n)
     (iter (for i in list)
            (finding i minimizing (abs (- i n)))
回复 原文
薄荷港 2024-07-18 12:08:56

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

41 characters in F#:

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

as in

#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
回复 原文
蔚蓝源自深海 2024-07-18 12:08:56

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

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

Ruby. One pass-through. Handles negative numbers nicely. Perhaps not very short, but certainly pretty.

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
回复 原文
~没有更多了~

关于作者

青春有你

暂无简介

文章
评论
25 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

佚名

文章 0 评论 0

羁客

文章 0 评论 0

天天爱笑的徐老师

文章 0 评论 0

星

文章 0 评论 0

夏日落

文章 0 评论 0

隐诗

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文