4

例：次のような配列があり[0,22,56,74,89]ます。別の番号に最も近い番号を見つけたいと思います。数がであるとしましょう72。この場合、配列の一番下の数は56であるため、それを返します。数値がの場合100、配列内の最大の数値よりも大きいため、最大の数値を返します。数値が22、の場合、それは完全に一致します。それを返すだけです。指定された数値が0を下回ることはなく、配列は常にソートされます。

私はこの質問を見ましたが、それは上向きまたは下向きのどちらかに近い方に最も近い数を返します。何があっても、一番近いものを下に戻してもらう必要があります。

どうすれば始められますか？どのロジックを使用する必要がありますか？

私のコードは毎秒実行され、すでに十分にCPUを集中的に使用しているため、ループが多すぎないことが望ましいです。

4

7 に答える 7

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 に答える
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 に答える
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 に答える
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 に答える
1

これは、OPが参照するreduceを使用したES6バージョンです。この回答に触発されて、配列から最も近い番号を取得します

ルックアップ配列は常にソートされるため、これは機能します。

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 に答える