4

示例：我有一个这样的数组：[0,22,56,74,89]我想找到最接近不同数字的数字。假设数字是72，在这种情况下，数组中最接近的数字是56，所以我们返回它。如果数字是100，那么它大于数组中的最大数字，所以我们返回最大的数字。如果数字是22，那么它是完全匹配的，只需返回即可。给定的数字永远不会低于 0，并且数组始终是排序的。

我确实看到了这个问题，但它返回最接近向上或向下的数字。无论如何，我必须让最近的一个向下返回。

我该如何开始？我应该使用什么逻辑？

最好不要太多循环，因为我的代码每秒运行一次，而且它已经足够占用 CPU。

4

7 回答 7

5 
var theArray = [0,22,56,74,89];
var goal = 56;
var closest = null;

$.each(theArray, function(){
  if (this <= goal && (closest == null || (goal - this) < (goal - closest))) {
    closest = this;
  }
});
alert(closest);

jsFiddle http://jsfiddle.net/UCUJY/1/

于 2013-03-04T14:44:08.883 回答
5

您可以对该值使用二进制搜索。改编自这个答案：

function index(arr, compare) { // binary search, with custom compare function
    var l = 0,
        r = arr.length - 1;
    while (l <= r) {
        var m = l + ((r - l) >> 1);
        var comp = compare(arr[m]);
        if (comp < 0) // arr[m] comes before the element
            l = m + 1;
        else if (comp > 0) // arr[m] comes after the element
            r = m - 1;
        else // arr[m] equals the element
            return m;
    }
    return l-1; // return the index of the next left item
                // usually you would just return -1 in case nothing is found
}
var arr = [0,22,56,74,89];
var i=index(arr, function(x){return x-72;}); // compare against 72
console.log(arr[i]);

顺便说一句：这是一个快速的性能测试（改编自 @Simon 的测试），它清楚地展示了二分搜索的优势。

于 2013-03-04T14:46:02.263 回答
2

这是一个没有 jQuery 的解决方案，可以提高效率。如果数组始终是排序的，则可以工作，无论如何都可以很容易地覆盖：

var test = 72,
    arr = [0,56,22,89,74].sort(); // just sort it generally if not sure about input, not really time consuming

function getClosestDown(test, arr) {
  var num = result = 0;

  for(var i = 0; i < arr.length; i++) {
    num = arr[i];
    if(num <= test) { result = num; }
  }

  return result;
}

逻辑：从最小的数字开始，result只要当前数字小于或等于测试单元就设置。

注意：只是出于好奇做了一些性能测试:)。在不声明函数的情况下将我的代码精简到基本部分。

于 2013-03-04T14:51:03.643 回答
2 
Array.prototype.getClosestDown = function(find) {            
    function getMedian(low, high) {
       return (low + ((high - low) >> 1));
    }

    var low = 0, high = this.length - 1, i;  

    while (low <= high) {
     i = getMedian(low,high);
     if (this[i] == find) { 
         return this[i]; 
     }        
     if (this[i] > find)  { 
         high = i - 1;
     }
     else  { 
         low = i + 1;
     }
  }  
  return this[Math.max(0, low-1)];
}

alert([0,22,56,74,89].getClosestDown(75));
于 2013-03-04T15:00:16.803 回答
1

这是一个使用reduce的ES6版本，OP引用。受此答案的启发，从数组中获取最接近的数字

查找数组总是排序的，所以这很有效。

const nearestBelow = (input, lookup) => lookup.reduce((prev, curr) => input >= curr ? curr : prev);
const counts = [0,22,56,74,89];
const goal = 72;
nearestBelow(goal, counts); // result is 56.

不如二分搜索快（很长一段路），但比循环和 jQuery grep https://jsperf.com/test-a-closest-number-function/7都好

于 2018-12-18T10:27:20.943 回答
0

正如我们知道数组已排序，我会将断言小于我们给定值的所有内容推送到临时数组中，然后返回其中的一个弹出窗口。

var getClosest = function (num, array) {
    var temp = [],
        count = 0,
        length = a.length;

    for (count; count < length; count += 1) {

        if (a[count] <= num) {
            temp.push(a[count]);
        } else {
            break;
        } 
    }

    return temp.pop();
}

getClosest(23, [0,22,56,74,89]);
于 2013-03-04T15:18:12.273 回答
0

这里是从@Simon 编辑的。它比较前后最接近的数字。

var test = 24,
arr = [76,56,22,89,74].sort(); // just sort it generally if not sure about input, not really time consuming

function getClosest(test, arr) {
  var num = result = 0;
  var flag = 0;
  for(var i = 0; i < arr.length; i++) {
    num = arr[i];
    if(num < test) {
      result = num;
      flag = 1;
    }else if (num == test) {
      result = num;
      break;
    }else if (flag == 1) {
      if ((num - test) < (Math.abs(arr[i-1] - test))){
        result = num;
      }
      break;
    }else{
      break;
    }
  }
  return result;
}
于 2013-12-15T18:09:27.033 回答