代码之家 › 专栏 › 技术社区 › danday74

JavaScript查找数组中小于等于给定数字的第一个数字

lodash javascript

danday74 · 技术社区 · 7 年前

const primes = [3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

我想找到此列表中的第一个数字<=给定的号码。

getHighestPrimeNumber(58) ... 应该返回53,是最大值也小于或等于58的素数

getHighestPrimeNumber(58)==53

getHighestPrimeNumber(52)==47

我目前的方法是迭代素数,但这是非常低效的,特别是考虑到列表中可能有10000多个数字-谢谢

香草JS或洛达斯就可以了

3 回复 | 直到 5 年前

Akrion 7 年前

lodash 琐碎的 由于 _.sortedIndex :

const primes = [3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

const closestPrime = (n) => {
  let index = _.sortedIndex(primes, n)
  return primes[index] == n ? primes[index] : primes[index-1]
}

console.log(closestPrime(58))
console.log(closestPrime(53))
console.log(closestPrime(52))

<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.17.10/lodash.min.js"></script>

Jacek Lipiec 7 年前

Binary search

const primes = [3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

function findHighestPrimeNumberRecursive(arr, ceiling) {
  const midpoint = arr.length/2
  if(arr[midpoint ] === ceiling){
    // we found it!
    return primes[arr.length-1];
  } else {
    if(arr[midpoint] <== ceiling) {
      return findHighestPrimeNumberRecursive(arr.slice(0, midpoint), ceiling);
    } else {
      return findHighestPrimeNumberRecursive(arr.slice(midpoint, arr.length), ceiling);
    }
  }
}

function getHighestPrimeNumber(ceiling) {
  return findHighestPrimeNumberRecursive(primes, ceiling);
}

ggorlen Hoàng Huy Khánh 7 年前

这是一项很好的任务 binary search

const bisect = (needle, haystack) => {
  let lo = 0;
  let hi = haystack.length;
  
  while (lo <= hi) {
    const mid = ~~((hi - lo) / 2 + lo);
    
    if (haystack[mid] === needle) {
      return needle;
    }
    else if (haystack[mid] > needle) {
      hi = mid - 1;
    }
    else {
      lo = mid + 1;      
    }
  }
  
  return haystack[hi];
};

const getHighestPrimeNumber = n => {
  const primes = [3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97];
  return bisect(n, primes);
};

console.log(getHighestPrimeNumber(58) === 53);
console.log(getHighestPrimeNumber(53) === 53);
console.log(getHighestPrimeNumber(52) === 47);

几点注意:

getHighestPrimeNumber 因此,它不会在每次函数调用时被创建和垃圾收集。此时,您不妨直接调用二进制搜索。
如果您关心数组边界上方和下方的查询,可以根据某些策略处理这些查询,例如: return haystack[Math.min(hi,haystack.length-1)]; .
二进制搜索的时间复杂度为O(nlog(n))。集合查找是O(1),因此如果您在阵列之外维护集合并首先尝试在那里查找,则可能会体验到性能提升。