先端とアルゴリズムleetcode 27.要素の除去

目次

フロントエンドとアルゴリズムleetcode 27.削除要素

テーマ記述

概要

ヒント

解析

アルゴリズム

先端とアルゴリズムleetcode 27.要素の除去
テーマの説明
27.要素の除去
概要
タイトル自体は簡単です.公式解答も " " と言っています.コピー配列なしで配列から要素を削除することは不可能だと思います.
ヒント
二重のポインタは長さだけを返します.元素の順序は変更できます.元素が少ない場合
解析
問題の現場削除を上書きとして理解します.つまり、私たちはvalと同じ値を見つけたら、彼を上書きします.だから、私たちは2つのポインタが必要です.一つの速いポインタは元素を探して比較します.一つの遅い針は元素を覆います.jsのlengthの特性を利用して、戻りの長さの前に配列の長さを直接設定します.このような利点は、配列の結果を直感的に見ることができ、真の意味での修正元配列を実現します.
アルゴリズム
ここでは、要素が少ない場合を考慮して、nums[j]が所与の値と異なるときにカバーされ、等しいときにlength--が同時にこの要素をスキップし、すなわち最も良い場合には、配列内のすべての要素がパラメータと等しくなると、lengthは0に減少してから直接に0に戻り、最悪の場合はすべての要素が等しくなく、すべてカバーされながらlengthに戻る.彼がjで指し示した数値で上書きしてiをインクリメントします.このプロセスはjが配列の最後に到達するまで繰り返します.配列の新しい長さはnums[j]!==valです.

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
const removeElement = (nums, val) => {
  if (nums.length === 0) return 0
  let { length } = nums
  let [i, j] = [0, 0]
  while (j < nums.length) {
    if (nums[j] !== val) {
      nums[i] = nums[j]
      i++
    } else {
      length--
    }
    j++
  }
  nums.length = length
  return length
}

着信lengthと3の運転結果

3
[ 1, 9, 6 ]

実行結果

     :64 ms,     javascript       91.87%    
     :33.7 MB,     javascript       33.58%