JavaScript находит первое число в массиве, которое <= к данному числу - PullRequest
Новая
       5

JavaScript находит первое число в массиве, которое <= к данному числу

0 голосов
/ 25 ноября 2018

У меня есть массив простых чисел: 

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]

Я хочу найти первое число в этом списке, которое <= заданное число. </p>

Например ... getHighestPrimeNumber(58) ... должен возвращать 53, являясь простым числом с наибольшим значением, которое также меньше или равно 58

Ожидаемые результаты:

getHighestPrimeNumber (58) === 53

getHighestPrimeNumber (53) === 53

getHighestPrimeNumber (52) === 47

Мой текущий подход состоит в том, чтобы перебирать простые числа, ноэто очень неэффективно, особенно если учесть, что в списке может быть более 10000 номеров - спасибо

Vanilla JS или Lodash - это хорошо

Ответы [ 3 ]

0 голосов
/ 25 ноября 2018

Похоже на поле для подхода «разделяй и властвуй».Что-то вроде двоичного поиска : 

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);
}
0 голосов
/ 25 ноября 2018

Поскольку вы опубликовали это с тегом 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>
0 голосов
/ 25 ноября 2018

Это хорошая задача для двоичного поиска : 

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, так что это не так.t создается и собирается при каждом вызове функции.На этом этапе вы можете просто вызвать бинарный поиск напрямую.
  • Если вас интересуют запросы, выходящие за пределы массива, вы можете обрабатывать их в соответствии с некоторой политикой, например: return haystack[Math.min(hi,haystack.length-1)];.
  • Бинарный поиск - это O (n log (n)) сложность времени.Поиск наборов - O (1), поэтому вы можете испытать повышение производительности, если вы сохраните набор в дополнение к массиву и сначала попытаетесь найти его там.
...