快速检查数字的方法是在一组数字的范围内。

Question

我只是遇到了下面这样的场景。听起来有点像个小编问题。

支持我可以得到一个模式的数字列表，以简化我的问题。

例如，[0, 5, 10, 15, 20, 25]或[0,7,14,21]，已经排序了。

然后给出一个range (我可以保证范围不会在两个连续的数字之间重叠)

例如，range=2；

如果是num=11，那么我支持获取index of 10，因为11在10-2到10+2的范围内。

如果是num=12.5，那么我只会返回-1或其他指示我们找不到的东西。

我可以简单地浏览列表并检查数字是否在每个数字的范围内，但是我觉得有一个O(1)解决方案，因为列表本身有一些模式存在。任何帮助都是非常感谢的。

还提供了Diff，上面的示例diff=5。

我现在没有遇到任何性能问题的O(N)列表检查，只是想让事情更好。

Answer 1

这是我对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("---------------------");
  }
}

​

实际上，如果我先建立索引，那就简单多了。然后，我们所需要做的就是从找到的索引的值中减去当前的数字，取其绝对值，看看它是否小于或等于给定的范围数。

​

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("---------------------");
  }
}

​

Answer 2

您可以使用Array.some检查数字(和范围)是否与列表重叠，例如：

这将是O(n)，我怀疑您确实需要一个非常大的列表来证明创建O(1)类型的解决方案是合理的。

我们可以走另一条路，创建一个候选数字数组(范围内的数字，例如10 +- 2，这将是8,9,10,11,12。注:这种方法将不适用于浮点值。

我们检查每个数字是否为从列表中创建的集合的成员。这在技术上仍然是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));

​