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

Question

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

Пример

Для sequence =[1, 3, 2, 1], вывод должен быть почтиIncreasingSequence (sequence) = false;

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

Для sequence = [1, 3, 2] выходные данные должны быть почтиIncreasingSequence (sequence) = true.

Вы можете удалить 3 из массива, чтобы получить строго возрастающую последовательность [1, 2],Кроме того, вы можете удалить 2, чтобы получить строго возрастающую последовательность [1, 3].

[input] array.integer sequence

Гарантированные ограничения: 2 ≤ sequence.length ≤ 105, -105≤ sequence [i] ≤ 105.

[output] логическое значение

функция nearIncreasingSequence (arr) {

for (let i = 0; i < arr.length; i++) {
    if (isSeq(arr.slice(0, i).concat(arr.slice(i + 1)))) {
        return true;
        break;
    }

}
return false

} ​​

function isSeq(subseq) {
    var sliced1 = subseq.slice(0, subseq.length - 1);
    var sliced2 = subseq.slice(1);
    return sliced1.every((el, index) => el < sliced2[index])

 }

Myкод медленныйКак можно улучшить.

Answer 1

Если это не , то это (ваша ссылка не работает и ответ не обновляется с требованиями).Тогда требования следующие:

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

Это оказалось сложнее, чем ожидалось.Нужно было некоторое время, чтобы разобраться с некоторыми неудачными крайними случаями, но на самом деле не удалось протестировать на codewars или codefights, потому что ссылки не будут загружаться без ошибок сервера.

Передайте checkFunction в функцию, которая будет проверять последовательность (массив)эта checkFunction получит текущий элемент в массиве и следующий элемент.В нашем случае checkFunction проверит, меньше ли текущий элемент, чем следующий элемент:

const increasing = isInSequence((current,next)=>current<next);

, который использует возвращаемое значение isInSequece, которое является частично примененной функцией с checkFunction, установленной на функцию, проверяющую текущий элемент меньше, чем next.

Если checkFunction не работает, то существует 4 ситуации:

1. [1,2,3,2] Последний и второй последний элемент не работает, просто удалите последний элемент
2. [1,10,2,3] Если текущий индекс равен 1 (число 10), то текущий будет проверен с помощью 2 и произойдет сбой.Лучше всего было бы удалить 10 (текущее).
3. [1,2,0,3] Если текущий индекс равен 1 (число 2), то 2 будет проверен на 0 и завершится ошибкой.Лучше всего было бы удалить 0 не текущий номер, а следующий
4. [2,1,2,3] Первый и второй элементы не пройдены, просто удалите первый.

Ситуации 1 и 4 не нуждаются в функции checkFunction, поскольку решение о том, какое число удалить, может быть принято в зависимости от currentIndex и array.length.В ситуациях 2 и 3 checkFunction используется с предыдущим и следующим значением, чтобы определить, лучше ли удалить текущий или следующий элемент:

//compare A with C in ABC where A is previous, B is current and C is next
//  we just failed to compare current with next (B with C)
array=(checkFunction(array[currentIndex-1],array[next]))
  //A with C passed, get rid of B
  ? [array[currentIndex-1]].concat(array.slice(next))
  //A with C failed, get rid of C (A with B passed)
  : [array[currentIndex]].concat(array.slice(next+1))

Вот весь код:

const isInSequence = checkFunction => (array,maxMissed) => {
  const recur = (missed,currentIndex,array) => {//compare lastIndex to next index
    if(currentIndex>=array.length-1) return true;//there is no next index to copare to
    var next = currentIndex+1;
    if(!checkFunction(array[next-1],array[next])){//compare
      missed++;
      if(next>=array.length-1){
        //compare to the last one failed, remove last
        array=array.slice(-1);
      }else if(currentIndex-1>=0) {
        //compare A with C in ABC where A is previous, B is current and C is next
        //  we just failed to compare current with next (B with C)
        array=(checkFunction(array[currentIndex-1],array[next]))
          //A with C passed, get rid of B
          ? [array[currentIndex-1]].concat(array.slice(next))
          //A with C failed, get rid of C (A with B passed)
          : [array[currentIndex]].concat(array.slice(next+1))
      }else{
        //There is no previous element from current so remove current
        array = array.slice(currentIndex);
      }
      next = 0;
    }
    if(missed>maxMissed){
      return false;//too many misses, return false
    }
    //recursively call itself
    return recur(missed,next,array);
  }
  return recur(0,0,array);
}

const test = (expected,value,message) =>
  (expected!==value)
    ? console.error("Failed, expected:",expected,"got:",value,"message:",message)
    : console.info("Passed:",message)
;
console.clear();
//partially apply isInSequence with a function that takes 2 arguments
//  and checks if argument one is smaller than argument 2
const increasing = isInSequence((current,next)=>current<next);
test(true,increasing([1,2,3],0),"1,2,3 should return true");
test(false,increasing([1,2,3,2],0),"1,2,3,2 should return false");
test(false,increasing([3,2],0),"3,2 should return false");
test(true,increasing([2,3],0),"2,3 should return true");
test(true,increasing([],0),"[] should return true");
test(true,increasing([2],0),"[2] should return true");
test(true,increasing([2,3,2],1),"2,3,2 should return true (can remove last one)");
test(true,increasing([2,1],1),"2,1 should return true (can miss one)");
test(false,increasing([1,2,1,3,2],1),"1,2,1,3,2 should return false (can only miss one)");
test(false,increasing([4,5,6,1,2,3],1),"4,5,6,1,2,3 should return false");
test(true,increasing([4,5,100,6,7],1),"4,5,100,6,7 should return true (remove 100 would work)");
test(false,increasing([5,1,5,2,3],1),"5,1,5,2,5,3 should return false");
test(true,increasing([1,2,0,3,2],2),"1,2,0,3,2 should return true (can miss two)");

Следующий код, который я добавил для полноты, поскольку мой код принимает значение maxMissed, которое может быть больше 1. В вашем случае вы можете пропустить только один, но если вы можете иметьболее одного пропуска, следующий случай ошибочно завершится неудачей [0,1,100,101,2,3,4,5] с двумя допустимыми пропусками:

const showDebug = false;
const debugLog = function(){
  if(showDebug){
    console.log.apply(window,Array.from(arguments));
  }
}
const isInSequence = checkFunction => (array,maxMissed) => {
  const recur = (missed,currentIndex,array) => {//compare lastIndex to next index
    debugLog("array:",array,"missed:",missed,"index:",currentIndex);
    if(currentIndex>=array.length-1) return true;//there is no next index to compare to
    var next = currentIndex+1;
    if(!checkFunction(array[next-1],array[next])){//compare
      debugLog("------------miss");
      missed++
      if(missed>maxMissed){
        return false;//too many misses, return false
      }
      if(next>=array.length-1){
        //compare to the last one failed, remove last
        array=array.slice(-1);
      }else if(currentIndex===0) {
        //There is no previous element from current so remove current
        array = array.slice(currentIndex+1);
      }else{
        //try again with current or next element removed, if either returns true
        //  then return true
        return recur(
          missed,0,array.slice(0,currentIndex).concat(array.slice(currentIndex+1))
        ) || recur(
          missed,0,array.slice(0,next).concat(array.slice(next+1))
        )
      }
      next = 0;
    }
    //recursively call itself
    return recur(missed,next,array);
  }
  return recur(0,0,array);
}

const test = (expected,value,message) =>
  (expected!==value)
    ? console.error("Failed, expected:",expected,"got:",value,"message:",message)
    : console.info("Passed:",message)
;
console.clear();
//partially apply isInSequence with a function that takes 2 arguments
//  and checks if argument one is smaller than argument 2
const increasing = isInSequence((current,next)=>current<next);
test(true,increasing([3,2,3],1),"3,2,3 should return true");
test(true,increasing([1,2,3],0),"1,2,3 should return true");
test(false,increasing([1,2,3,2],0),"1,2,3,2 should return false");
test(true,increasing([2,3],0),"2,3 should return true");
test(true,increasing([],0),"[] should return true");
test(true,increasing([2],0),"[2] should return true");
test(true,increasing([2,3,2],1),"2,3,2 should return true (can remove last one)");
test(true,increasing([2,1],1),"2,1 should return true (can miss one)");
test(false,increasing([1,2,1,3,2],1),"1,2,1,3,2 should return false (can only miss one)");
test(false,increasing([4,5,6,1,2,3],1),"4,5,6,1,2,3 should return false");
test(true,increasing([4,5,100,6,7],1),"4,5,100,6,7 should return true (remove 100 would work)");
test(false,increasing([5,1,5,2,3],1),"5,1,5,2,5,3 should return false");
test(true,increasing([1,2,0,3,2],2),"1,2,0,3,2 should return true (can miss two)");
test(false,increasing([3,2],0),"3,2 should return false");

// less performant version to fix this edge case (not your problem since only 1 can fail in your case)
test(true,increasing([0,1,100,101,2,3,4,5],2),"0,1,100,101,2,3,4,5 should return true (can miss two)");

Answer 2

Ваше решение создает новые массивы при использовании slice(), что требует больше времени.Чтобы решить проблему, вам просто нужно проверить, истинно ли arr[x] > arr[x+1] дважды .Вам не нужно изменять массив.

let count = 0, highest = 0;
for(let x=0; x < arr.length - 1; x++) {
     highest = Math.max(highest, arr[x]);
     if(highest > arr[x+1]) {
        if(++count === 2) {
           return false;
        }
     }
}
return true;