毎日のアルゴリズム: 有効な三角形の数

[[429712]]

この記事はWeChatの公開アカウント「3分でフロントエンドを学ぶ」から転載したもので、著者はsisterAnです。この記事を転載する場合は、「3分で学ぶフロントエンド」公式アカウントまでご連絡ください。

負でない整数を含む配列が与えられた場合、三角形の 3 辺を形成できる 3 つ組の数を数えることがタスクです。

例1:

入力: [2,2,3,4]
出力: 3
説明する：
有効な組み合わせは次のとおりです。
 2、3、4（最初の2つを使用）
 2、3、4（2番目の2を使用）
 2,2,3

知らせ：

• 配列の長さは 1000 を超えることはできません。
• 配列内の整数の範囲は[0, 1000]です。

解決策: ソート + ダブルポインタ

三角形のどの2辺の合計も3番目の辺より大きく、どの2辺の差も3番目の辺より小さいことがわかっています。3辺の長さを小さい方から順にa、b、cとすると、これらの3辺はa + b > cの場合にのみ三角形を形成できます。

解決策: 最初に配列をソートし、次に最長のエッジを固定し、ダブル ポインター メソッドを使用して残りのエッジを決定します。

nums[nums.length - 1]を最長辺nums[k]とする（k = nums.length - 1）

nums[i]を最短辺とし、nums[nums.length - 2]を2番目の数nums[j]（j = nums.length - 2）とする。

nums[i] + nums[j]がnums[k]より大きいかどうかを判定します。

• nums[i] + nums[j] > nums[k] の場合、次のようになります。

数値[i+1] + 数値[j] > 数値[k]
数値[i+2] + 数値[j] > 数値[k]
 ...
数値[j-1] + 数値[j] > 数値[k]

そして、ji に三角形を形成できる三つ組の数が追加され、j が一つ前の位置 (j--) に移動し、次のラウンドの判定が続行されます。

• nums[i] + nums[j] <= nums[k]の場合、lは1つ後ろに移動し（numsは昇順）、判定を続けます。

コード実装:

 triangleNumber = function (nums) {とします。
    if (!nums || nums.length < 3) 0を返す
    カウントを 0 にする
    // 選別
    nums.sort((a, b) => a - b)
 (k = nums.length - 1; k > 1; k --)の場合{  
        i = 0、j = k - 1とする
        i < j の場合{
            if(nums[i] + nums[j] > nums[k]){
カウント+= j - i
                じ --  
            }それ以外{
                私は++
            }
        }
    }
戻る カウント 
 }

複雑性分析:

• 時間計算量: O(n^2^)
• 空間計算量: O(n)

知らせ：

Array.prototype.sort() に関しては、ES 仕様では特定のアルゴリズムは指定されていません。バージョン 7.0 より前の V8 エンジンでは、配列の長さが 10 未満の場合、Array.prototype.sort() は挿入ソートを使用し、それ以外の場合はクイックソートを使用します。

クイックソートは安定したソートアルゴリズムではないため、V8 エンジンバージョン 7.0 以降では廃止されました。最悪の場合、時間計算量は O(n2) に低下します。

代わりに、ハイブリッド ソート アルゴリズムである TimSort が使用されます。

この機能アルゴリズムは、もともと Python 言語で使用されていました。厳密に言えば、上記の 10 個のソート アルゴリズムのいずれにも属さず、ハイブリッド ソート アルゴリズムです。

データ量の少ないサブ配列では挿入ソートを使用し、次にマージソートを使用して順序付けられたサブ配列をマージしてソートします。時間の計算量は O(nlogn) です。

リートコード: https://leetcode-cn.com/problems/valid-triangle-number/solution/teng-xun-leetcode611you-xiao-san-jiao-xing-de-ge-s/