Finding the closest number in a random set

问题:

Say I got a set of 10 random numbers between 0 and 100.

An operator gives me also a random number between 0 and 100. Then I got to find the number in the set that is the closest from the number the operator gave me.

example

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

operator number = 45

return = 39

And how do translate this into code? (javascript or something)

回答1:

if set is ordered, do a binary search to find the value, (or the 2 values) that are closest. Then distinguish which of 2 is closest by ... subtracting?

If set is not ordered, just iterate through the set, (Sorting it would itself take more than one pass), and for each member, check to see if the difference is smaller than the smallest difference you have seen so far, and if it is, record it as the new smallest difference, and that number as the new candidate answer. .

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

回答2:

• given an array called input, create another array of the same size
• each element of this new array is the Math.abs(input[i] - operatorNumber)
• select the index of the mininum element (let's call it k)
• your answer is input[k]

NB

• sorting is not needed
• you can do it without the extra array

Sample implementation in 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;
}

回答3:

How about this:

1) Put the set into a binary tree.
2) Insert the operator number into the tree
3) Return the Operators parent

回答4:

1. order the set
2. binary search for the input
3. if you end up between two elements, check the difference, and return the one with the smallest difference.

回答5:

Someone tagged this question Mathematica, so here's a Mathematica answer:

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

It works when there are multiple elements of set equally distant from the operator number.

回答6:

python example:

#!/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