Получение значения из ключа в словаре, ближайшем к заданному числу, с использованием JavaScript - PullRequest
Новая
       13

Получение значения из ключа в словаре, ближайшем к заданному числу, с использованием JavaScript

3 голосов
/ 30 октября 2009

У меня есть словарь (ключи целые, значения с плавающей запятой). Я бы сейчас спросил в словаре значение ключа, которое> чем заданное число, но <чем следующий больший ключ. </p>

Пример:

dict = {100: 0,0035, 150: 0,0024, 200: 0,0019}.

я даю 122, это должно дать мне 0,0035

я даю 333, это должно дать мне 0,0019

я даю 200, это должно дать мне 0,0024

Спасибо!

Ответы [ 6 ]

1 голос
/ 30 октября 2009

Это идеальный вариант использования для двоичного дерева. Эта тема немного широка для ответа о переполнении стека, но все равно идет дальше. 

function addValueToNode(tree, nodeidx, value) {
    var left = 2*nodeidx + 1;
    var right = 2*nodeidx + 2;

    if(value > tree[nodeidx]) {
        if(!tree[right])
            tree[right] = value;
        else
            addValueToNode(tree, right, value);
    } else {
        if(!tree[left])
            tree[left] = value;
        else
            addValueToNode(tree, left, value);
    }
}

function addValueToTree(tree, value) {
    if(tree.length == 0)
        tree.push(value)
    else
        addValueToNode(tree, 0, value);
}

function addValuesToTree(tree, values) {
    for(var i = 0; i < values.length; i++)
        addValueToTree(tree, values[i]);
}

function addDictionaryToTree(tree, dict) {
    var values = [];
    for(var key in dict) {
        values.push(key);
    }
    values.sort();
    addValuesToTree(tree, values);
}

function findClosestValue(tree, nodeidx, value) {
    var left = 2*nodeidx + 1;
    var right = 2*nodeidx + 2;

    if(value > tree[nodeidx]) {
        if(!tree[right] || tree[right] == value)
            return tree[nodeidx];
        else
            return findClosestValue(tree, right, value);
    } else {
        if(!tree[left])
            return tree[nodeidx];
        else
            return findClosestValue(tree, left, value);
    }
}
var tree = [];
var dict = {100: 0.0035, 150: 0.0024, 200: 0.0019};

addDictionaryToTree(tree, dict);

var closest = findClosestValue(tree, 0, 175);
var dictValue = dict[closest];

alert( closest + " : " + dictValue);
0 голосов
/ 30 октября 2009

Двоичный поиск с использованием модифицированного (стабильного) алгоритма, который ищет наименьший элемент, соответствующий критериям сравнения.

0 голосов
/ 30 октября 2009

Следующая функция соответствует вашим требованиям: 

function getNumber(dict, value) {
  var key, found;

  for (key in dict) {
    if (value - key > 0) {
      found = key;
    }
  }
  return dict[found];
}

var dict = {100: 0.0035, 150: 0.0024, 200: 0.0019};

// Firebug assertions
console.assert(getNumber(dict, 122) == 0.0035);
console.assert(getNumber(dict, 333) == 0.0019);
console.assert(getNumber(dict, 200) == 0.0024);
0 голосов
/ 30 октября 2009

Рабочий пример (протестирован под Firefox 3.6): 

<html>
<head>
<script type="text/javascript" src="jquery-1.3.2.min.js"></script>
<script type="text/javascript">
var dict = {100: 0.0035, 150: 0.0024, 200: 0.0019};

function r(aNum) {
    var result;

    for (var key in dict) {
        var dist = key - aNum

        if ((dist < 0 && dist < result) || result === undefined) {
            result = key;
        }
    }

    return dict[result];
}

$(document).ready(function() {
    $('li').each(function() {
        var id = $(this).attr('id').replace('n', '')
        $(this).html(id + ": " + r(id));
    });
});
</script>
</head>
<body>
    <ul>
        <li id="n122"></li>
        <li id="n333"></li>
        <li id="n200"></li>
    </ul>
</body>
</html>
0 голосов
/ 30 октября 2009 
var value = 122;
var min = null;
var minkey = null;
for ( var key : dict ) {
  if (min==null || abs(value-key)<min) {
      min=abs(value-key);
      minkey = key;
  }
}
return dict[minkey]

Вы можете попробовать это. Извините, если что-то, у меня нет шансов проверить это.

0 голосов
/ 30 октября 2009

Если ваш словарь невелик, вы можете попробовать выполнить цикл, например, (122-1). Если он не определен, вычтите 1 и попробуйте снова, пока не найдете что-то:)

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...