быстрый способ проверить, что число находится в диапазоне группы чисел

Question

Я столкнулся со сценарием вроде следующего. Это немного похоже на вопрос leetcode.

Поддержка Я могу получить список номеров в шаблоне, чтобы упростить мои вопросы.

Например, [0, 5, 10, 15, 20, 25] или [0,7,14,21], он уже отсортирован.

затем задано range (я могу гарантировать, что диапазон никогда не будет перекрываться между двумя последовательными числами)

например, range=2;

If num=11, то я поддерживаю получение index of 10, потому что 11 находится в диапазоне от 10-2 до 10+2.

Если num=12.5, я просто верну -1 или что-нибудь еще чтобы указать, что мы не находим.

Я могу просто go просмотреть список и проверить, находится ли число в диапазоне каждого числа, но я чувствую, что существует решение O (1), поскольку сам список есть какой-то шаблон. Приветствуется любая помощь.

Diff также предоставляется, приведенный выше пример diff=5.

Я не сталкиваюсь с проблемой производительности сейчас с проверкой списка O (N), просто хочу чтобы улучшить ситуацию.

Answer 1

Вы можете использовать Array.some , чтобы проверить, совпадает ли число (и диапазон) с вашим списком, например:

Это будет O (n), и я подозреваю, что вы действительно понадобится очень большой список, чтобы оправдать создание решения типа O (1).

Мы можем go наоборот, создав массив номеров кандидатов (числа в пределах диапазона, например, для 10 + - 2 это будет [8,9,10,11,12]. NB: этот подход не будет работать для значений с плавающей запятой.

Мы проверяем каждое число на предмет принадлежности к набору, созданному из списка. Это будет все еще технически O (n), но N, скорее всего, будет маленьким (например, 5).

let list = [0, 5, 10, 15, 20, 25];

// This solution will need at most N iterations, where N is the length of list
function checkInRange(value, range, list) {
    return list.some((el) => {
        return (el >= (value - range)) && (el <= (value + range));
    })
}

// This solution will need at most N iterations, where N is the length of a, e.g. 2 * range + 1
function checkInRangeSet(value, range, list) {
    // Create an array of matching numbers, e.g. 8,9,10,11,12
    let a = Array.from({ length: 2*range + 1 }, (v,k) => value - range + k);
    let set = new Set(list);
    return a.some((el) => {
        return set.has(el);
    })
}

console.log("Solution with simple loop");
console.log(checkInRange(11, 1, list));
console.log(checkInRange(10, 0, list));
console.log(checkInRange(30, 5, list));

console.log(checkInRange(9, 0, list));
console.log(checkInRange(100, 20, list));


console.log("Solution with Set");
console.log(checkInRangeSet(11, 1, list));
console.log(checkInRangeSet(10, 0, list));
console.log(checkInRangeSet(30, 5, list));

console.log(checkInRangeSet(9, 0, list));
console.log(checkInRangeSet(100, 20, list));

Answer 2

Вот мой шанс на решение O (1).

const list = [0, 7, 14, 21, 28];
const interval = list[1];
const range = 2;

function getIndex(num, range) {
  const halfItvl = interval / 2;
  const inRange = Math.abs((num % interval) - halfItvl) >= halfItvl - range;

  return inRange ? Math.trunc((num + halfItvl) / interval) : -1;
}


// Test for all numbers within the list
for (var i = 0; i < list[list.length - 1]; i++) {
  const res = getIndex(i, range);

  if (res === -1) {
    console.log(`${i} is out of range ${range}`);
  } else {
    console.log(`${i} is within range ${range} of index ${res}`);
  }

  if (i % interval === interval - 1) {
    console.log("---------------------");
  }
}

На самом деле, это кажется немного проще, если я сначала установлю sh индекс. Затем все, что нам нужно сделать, это вычесть текущее число из значения в найденном индексе, взять его абсолютное значение и посмотреть, меньше ли оно или равно заданному номеру диапазона.

const list = [0, 7, 14, 21, 28];
const interval = list[1];
const range = 2;

function getIndex(num, range) {
  const idx = Math.trunc((num + (interval / 2)) / interval);
  
  return Math.abs(list[idx] - num) <= range ? idx : -1;
}


// Test for all numbers within the list
for (var i = 0; i < list[list.length - 1]; i++) {
  const res = getIndex(i, range);

  if (res === -1) {
    console.log(`${i} is out of range ${range}`);
  } else {
    console.log(`${i} is within range ${range} of index ${res}`);
  }

  if (i % interval === interval - 1) {
    console.log("---------------------");
  }
}