Finding closest match in collection of numbers [cl

问题:

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.

回答1:

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

回答2:

Shorter Python: 41 chars

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

回答3:

My attempt in python:

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

回答4:

Groovy 28B

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

回答5:

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

回答6:

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.

回答7:

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;

回答8:

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

回答9:

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

回答10:

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

回答11:

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

回答12:

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.

回答13:

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  

回答14:

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]

回答15:

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

回答16:

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.

回答17:

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

回答18:

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

回答19:

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

回答20:

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];
}

回答21:

Here's another Haskell answer:

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

回答22:

Haskell, 60 characters -

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

回答23:

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

回答24:

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

回答25:

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

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

回答27:

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.

回答28:

Common Lisp using iterate library.

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

回答29:

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

回答30:

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