Как эффективно проверить, отсутствует ли список последовательных номеров каких-либо элементов

Ответ 1

Поскольку вы знаете, что ожидаете последовательный массив, я не знаю, почему это должно быть сложнее, чем цикл через числа arr[0] через arr[end] то время как счетчик не знает, где вы находитесь в массиве. Это будет работать на O (n), но я не думаю, что вы можете улучшить это - вам нужно смотреть на каждый элемент хотя бы один раз в худшем случае.

var arr = ["s00","s01","s02","s03","s04","s05","s07","s08","s09","s10","s11","s12","s13","s14","s17","s19","s20","s21","s22","s24","s25","s26","s27","s28","s30","s32","s33","s34","s36","s38","s39","s41","s43","s44","s45","s46","s47","s48","s49","s50","s51","s52","s53","s54","s55","s56","s58","s60","s61","s62","s63","s64","s65","s67","s69","s70"];

let first = parseInt(arr[0].substring(1))
let last =  parseInt(arr[arr.length-1].substring(1))
let count = 0
for (let i = first; i< last; i++) {
   if (parseInt(arr[count].substring(1)) == i) {count++; continue}
   else console.log('seem to be missing ${'s'+i.toString().padStart(2,'0')} between: ${arr[count-1]} and ${arr[count]}' )
}

Ответ 2

Насколько я понимаю из вашего решения идеального массива, вы знаете максимальный размер массива (?). Поэтому, если у вас есть 100 максимальных значений и ожидайте S00 - S99, вы можете сделать:

var arrayIndex=0;
for (var i =0; i<100;i++) {
   var idealValue="s"+("00"+i).slice(-2); // To get S01-S99
   if(arr.length <= arrayIndex || arr[arrayIndex]!=idealValue){
        console.log(idealValue + 'is missing');
   }
   arrayIndex++;
}

Или что-то типа того. Я не могу проверить его прямо сейчас;) Но перебирайте список идеальных значений и сравнивайте одно и то же значение в массиве. Если он не соответствует его печати.

Ответ 3

Ваше решение с внутренним, в while -loop кажется уже неплохим, просто оставьте ненужное if и отслеживайте число, которое вы ожидаете видеть, вместо того, чтобы каждый раз разбирать предыдущий номер.

Что-то вроде этого:

var arr = ["s00","s01","s02","s03","s04","s05","s07","s08","s09","s10","s11","s12","s13","s14","s17","s19","s20","s21","s22","s24","s25","s26","s27","s28","s30","s32","s33","s34","s36","s38","s39","s41","s43","s44","s45","s46","s47","s48","s49","s50","s51","s52","s53","s54","s55","s56","s58","s60","s61","s62","s63","s64","s65","s67","s69","s70"];
var expectedI = 0
for (var i = 0; i < arr.length; i++) {
  var currentI = parseInt(arr[i].toLowerCase().split("s")[1]);
  while (expectedI < currentI) {
    console.log('Seems like ${expectedI} is missing.')
    expectedI++
  }
  expectedI = currentI + 1
}

Ответ 4

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

const
    getNumber = s => +s.slice(1),
    pad = i => ('00' + i).slice(-2);

var array = ["s00", "s01", "s02", "s03", "s04", "s05", "s07", "s08", "s09", "s10", "s11", "s12", "s13", "s14", "s17", "s19", "s20", "s21", "s22", "s24", "s25", "s26", "s27", "s28", "s30", "s32", "s33", "s34", "s36", "s38", "s39", "s41", "s43", "s44", "s45", "s46", "s47", "s48", "s49", "s50", "s51", "s52", "s53", "s54", "s55", "s56", "s58", "s60", "s61", "s62", "s63", "s64", "s65", "s67", "s69", "s70"],
    result = [];

array.reduce((left, right) => {
    var l = getNumber(left),
        r = getNumber(right);

    while (++l < r) {
        result.push('s' + pad(l));
    }
    return right;
});

console.log(result);

Ответ 5

Это всего лишь подход для поиска, если в заданном массиве отсутствует какой-либо элемент в числовой последовательности. Мы могли бы использовать (n * (n + 1))/2, которые разрешали сложение на n первых чисел. Кроме того, если массив начинается с примера 10, мы удаляем 1-10 сумм. Это просто говорит нам, если что-то отсутствует, но не то, что отсутствует. Преимущество состоит в том, что массив может быть несортирован. Вычислить минимум менее дорого, чем заказать весь массив.

var arr = ["s00","s01","s02","s03","s04","s05","s07","s08","s09","s10","s11","s12","s13","s14","s17","s19","s20","s21","s22","s24","s25","s26","s27","s28","s30","s32","s33","s34","s36","s38","s39","s41","s43","s44","s45","s46","s47","s48","s49","s50","s51","s52","s53","s54","s55","s56","s58","s60","s61","s62","s63","s64","s65","s67","s69","s70"];

let total = 0;

for(let i = 0; i<arr.length; i++){
    arr[i] = parseInt(arr[i].replace("s", ""));
    total += arr[i];
}

let hipFirstSum = ((arr[0]-1)*(arr[0]))/2;  //or minimun
let n = arr[arr.length -1];
let hipSum = (n*(n+1))/2;
let realSum = hipSum - hipFirstSum;

(realSum != total)?console.log("wrong"):console.log("good");

Ответ 6

Вы можете перейти к чему-то подобному, который сравнивает каждый элемент массива с рядом с ним, а затем, если разница больше 1, все зарегистрированные цифры могут быть зарегистрированы.

const arr = ["s00", "s01", "s02", "s03", "s04", "s05", "s07", "s08", "s09", "s10", "s11", "s12", "s13", "s14", "s17", "s19", "s20", "s21", "s22", "s24", "s25", "s26", "s27", "s28", "s30", "s32", "s33", "s34", "s36", "s38", "s39", "s41", "s43", "s44", "s45", "s46", "s47", "s48", "s49", "s50", "s51", "s52", "s53", "s54", "s55", "s56", "s58", "s60", "s61", "s62", "s63", "s64", "s65", "s67", "s69", "s70"];

for (let i = 0; i < arr.length - 1; i++) {
  let currentNum = parseInt(arr[i].split("s")[1]);
  let difference = parseInt(arr[i + 1].split("s")[1]) - currentNum;
  if (difference === 1) continue

  for (let d = 1; d < difference; d++)
    console.log('Seems likes ${currentNum+d} is missing')
}

Ответ 7

Вот рекурсивный подход, основанный на принятом ответе, но реорганизованный для возврата данных:

var arr = ["s00", "s01", "s02", "s03", "s04", "s05", "s07", "s08", "s09", "s10", "s11", "s12", "s13", "s14", "s17", "s19", "s20", "s21", "s22", "s24", "s25", "s26", "s27", "s28", "s30", "s32", "s33", "s34", "s36", "s38", "s39", "s41", "s43", "s44", "s45", "s46", "s47", "s48", "s49", "s50", "s51", "s52", "s53", "s54", "s55", "s56", "s58", "s60", "s61", "s62", "s63", "s64", "s65", "s67", "s69", "s70"];

function findMissing(arr, l, r) {
  var lval = Number(arr[l].substr(1));
  var rval = Number(arr[r].substr(1));
  // the segment has no gaps
  if (r - l === rval - lval) {
    return [];
  }
  // the segment has exactly two items
  if (r - l === 1) {
    return Array.from({ length: rval - lval - 1 }, function(x, i) {
      return "s" + (lval + 1 + i);
    });
  }
  // calculate middle using integer cast trick
  var m = (l + r) / 2 | 0;
  // process the segments [l, m] and [m, r]
  // note that m is processed twice and requires extra recursion
  // however this eliminates the extra coding needed to handle
  // the case where m and m + 1 are not consecutive
  return findMissing(arr, l, m).concat(findMissing(arr, m, r));
}
var result = findMissing(arr, 0, arr.length - 1);
console.log(result);

Ответ 8

Эта версия заполняет массив всеми возможными значениями, а затем выбирает отсутствующие:

var arr = ["s00","s01","s02","s03","s04","s05","s07","s08","s09","s10","s11","s12","s13","s14","s17","s19","s20","s21","s22","s24","s25","s26","s27","s28","s30","s32","s33","s34","s36","s38","s39","s41","s43","s44","s45","s46","s47","s48","s49","s50","s51","s52","s53","s54","s55","s56","s58","s60","s61","s62","s63","s64","s65","s67","s69","s70"];

var fullArray = Array(71).fill().map((item, index) => "s"+(""+(0 + index)).padStart(2,"0"));

var missingValues = fullArray.filter( ( el ) => !arr.includes( el ) );

console.log(missingValues);

Ответ 9

Javascript версия программы C выше, которая позволяет использовать последовательности отсутствующих элементов.

var util = require( 'util' );

//  Array of data.
var arr = [
        1,  2,  3,  4,  5,  6,  7,  8,  9,
    10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
    20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
    30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
    40, 41, 42, 43,         46, 47, 48, 49,
    50, 51, 52, 53, 54, 55, 56, 57, 58, 59,
    60, 61, 62, 63, 64, 65, 66, 67, 68, 70
];
var arr_len = arr.length;

//  Empty array?
if (arr_len == 0)
{
    console.log(
        util.format(
            "No elements." ));
    process.exit( 0 );
}

//  Pre-check.
var lim = arr[arr_len - 1] - (arr_len - 1);
if (lim == 0)
{
    printf(
        "No missing elements.\n" );
    return 0;
}

//  Initialize binary search.
var lo  = 0;
var hi  = arr_len;
var mid = 0;

//  Search metadata.
var cnt = 0;
var prv = 0;
var val = 0;
var i;

for (i = 0; i < arr_len && cnt < lim; i++)
{
    //  Get mid point of search.
    mid = (lo + hi) >> 1;

    //  Get array value, adjust and do comparisons
    val = arr[ mid ] - cnt;
    if (val === mid)
        lo = mid + 1;
    if (val > mid)
        hi = mid - 1;

    //  Have we found something?
    if (lo > hi)
    {
        //  Yes.  Divide and conquer.
        hi  = arr_len;
        prv = cnt;
        cnt = arr[ lo ] - lo;

        //  Report missing element(s).
        console.log(
            util.format(
                "Missing %d elements @ arr[ %d ] == %d, probes = %d",
                cnt - prv,
                lo,
                arr[ lo ],
                i + 1 ));
    }
}

console.log(
    util.format(
        "Probes: %d",
        i ));

Ответ 10

Быстрое и простое решение - объединить все элементы массива в строку и затем выполнить поиск внутри этой строки.

Вот решение, которое принимает массив (упорядоченный или неупорядоченный, отлично работает в любом случае) с любым шаблоном (не требуется жестко закодированный шаблон s0x):

    const arr = ["s00","s01","s02","s03","s04","s05","s07","s08","s09","s10","s11","s12","s13","s14","s17","s19","s20","s21","s22","s24","s25","s26","s27","s28","s30","s32","s33","s34","s36","s38","s39","s41","s43","s44","s45","s46","s47","s48","s49","s50","s51","s52","s53","s54","s55","s56","s58","s60","s61","s62","s63","s64","s65","s67","s69","s70"];
    let firstIndex = Number(arr[0].replace(/\D/, ''));
    let lastIndex = Number(arr[arr.length-1].replace(/\D/, ''));
    let separator = ',';
    
    let arrString = separator + arr.join(separator) + separator;
    for (let i = firstIndex; i <= lastIndex; i++) {
    	let element = arr[0].slice(0, arr[0].length - String(i).length) + i;
    
    	if (arrString.indexOf(separator + element + separator) < 0) {
			console.log(element)
    	}
    }

Ответ 11

Использование массива булевых элементов для отслеживания присутствующих элементов:

let numbers = arr.map(s => +s.slice(1)); // Convert to numbers
let maximum = Math.max.apply(null, numbers); // Get the maximum
let missing = Array(maximum).fill(true); // start with all missing
let answer = numbers.reduce((p, c) => (p[c] = false, p), missing); // set to false if there
answer.forEach((e,i) =>  (e && console.log(i + " seems to be missing"))); // show answer

Также работает для случайно упорядоченных номеров.

Ответ 12

Итак, если вы знаете, что нет дубликатов и что записи в порядке, довольно простой процесс - начать с проверки количества элементов в списке.

Длина arr должна быть равна числу последовательных элементов, да?

*** Предостережение. Если элементы не отсортированы или могут быть дубликаты, это, конечно, не сработает.

Предполагая, что условия применимы, простой двоичный поиск найдет первый отсутствующий элемент.

После этого это разделение и победа, при этом двоичный поиск ограничивается верхней частью пространства поиска, чтобы найти следующий недостающий элемент. Рекурсивный алгоритм будет легко понять, но вы также можете сделать это в одной функции.

Обратите внимание, что элементы содержат взаимосвязь между их индексами списка. В вашем двоичном поиске, если "s08" находится в элементе семь, то вы знаете, что в массиве отсутствует элемент раньше.

Бинарный поиск довольно прост, и, вероятно, он будет пользоваться менее наивным способом сравнения, так как элементы являются фиксированной полевой строкой.

Регулировка отсутствующих элементов также довольно проста. Каждый недостающий элемент сдвигает остальные элементы на один индекс слева, поэтому он превращается в простое целочисленное действие.

Шутки в сторону? Это не так сложно:

#include    <stdio.h>
#include    <stdlib.h>

#define ARY_SZ  68

static
int arr[ARY_SZ] =
{
        1,  2,  3,  4,  5,  6,  7,  8,  9,
    10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
    20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
    30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
    40, 41, 42, 43,     45, 46, 47, 48, 49,
    50, 51, 52, 53, 54, 55, 56, 57, 58, 59,
    60, 61, 62, 63, 64, 65, 66, 67, 68, 70
};

int
main(
    void )
{
    int     i,
            lim,
            lo,
            hi,
            mid,
            val,
            cnt;

    /*  Pre-check.  */
    lim = arr[ARY_SZ - 1] - (ARY_SZ - 1);
    if (lim == 0)
    {
        /*  No missing elements.    */
        printf(
            "No missing elements.\n" );
        return 0;
    }

    /*  Initialize binary search.   */
    lo  = 0;
    hi  = ARY_SZ;
    cnt = 0;

    /*  For (at most) the number of array elements, do: */
    for (i = 0; i < ARY_SZ && cnt < lim; i++)
    {
        /*  Get mid point of search.    */
        mid = lo + hi >> 1;

        /*  Get array value, adjust and do comparisons. */
        val = arr[ mid ] - cnt;
        if (val == mid)
            lo = mid + 1;
        if (val > mid)
            hi = mid - 1;

        if (lo > hi)
        {
            /*  Report missing element. */
            printf(
                "Missing element @ arr[ %d ] == %d, probes = %d\n",
                lo,
                arr[ lo ],
                i );

            /*  Divide and conquer. */
            hi   = ARY_SZ;
            cnt += 1;
        }
    }

    printf(
        "Probes = %d\n",
        i - 1);

    return 0;
}

Результаты компиляции этого C-кода и его запуск:

Missing element @ arr[ 0 ] == 1, probes = 5
Missing element @ arr[ 43 ] == 45, probes = 11
Missing element @ arr[ 67 ] == 70, probes = 16
Probes = 16

Таким образом, не требуется никакого линейного поиска и максимум 16 зондов, необходимых для нахождения трех отсутствующих элементов.