K サイズの部分配列の検出力を求める I

3254。 K サイズの部分配列の検出力を求める I

難易度: 中

トピック: 配列、スライディング ウィンドウ

長さ n の整数 nums と 正の 整数 k の配列が与えられます。

配列の 電力 は次のように定義されます:

• すべての要素が 連続 であり、昇順 順にソートされている場合の 最大 要素。
• それ以外の場合は -1。

サイズ k の数値のすべての部分配列1の^累乗を見つける必要があります。

サイズ n - k 1 の整数配列結果を返します。ここで、results[i] は nums[i..(i k - 1)] の 累乗です。

例 1:

• 入力: nums = [1,2,3,4,3,2,5]、k = 3
• 出力: [3,4,-1,-1,-1]
• 説明: サイズ 3 の num の部分配列が 5 つあります。
  • [1, 2, 3] の最大要素は 3.
  • [2, 3, 4] 最大要素 4.
  • [3, 4, 3] の要素は連続していません。
  • [4, 3, 2] の要素はソートされていません。
  • [3, 2, 5] の要素は連続していません。

例 2:

• 入力: nums = [2,2,2,2,2]、k = 4
• 出力: [-1,-1]

例 3:

• 入力: nums = [3,2,3,2,3,2]、k = 2
• 出力: [-1,3,-1,3,-1]

制約:

• 1
• 1 5
• 1

ヒント:

1. ネストされたループと HashSet を使用したブルート フォース ソリューションを使用できますか?

解決策:

タスクは次のように分類できます:

問題の内訳:

1. 長さ n の配列 nums と正の整数 k が与えられます。サイズ k のすべての部分配列を考慮し、それらのべきを計算する必要があります。
2. 部分配列の べき乗 は次のとおりです。
   • すべての要素が 連続 であり、昇順 順にソートされている場合の部分配列の 最大 要素。
   • それ以外の場合は -1。
3. サイズ n - k 1 の配列を返す必要があります。ここで、各要素はそれぞれの部分配列のべき乗に対応します。

プラン：

1. スライディング ウィンドウ アプローチ: 配列上をスライドして、長さ k の各部分配列をチェックします。
2. 部分配列がソートされているかどうかを確認します: 部分配列に連続した要素があり、昇順にソートされているかどうかを確認する必要があります。
3. 最大値または -1 を返す: 部分配列が有効な場合は、最大要素を返します。それ以外の場合は、-1 を返します。

手順:

1. 部分配列がソートされているかどうかを確認します:
   連続した要素を持つソートされた部分配列には、部分配列内のすべての i に対して nums[i 1] - nums[i] == 1 というプロパティが必要です。
2. スライディング ウィンドウ:
   長さ k の各部分配列について、ソートされているかどうかを確認し、有効な場合は最大の要素を返し、そうでない場合は -1 を返します。

このソリューションを PHP で実装してみましょう:

3254。 K サイズの部分配列の検出力を求める I

<?php
/**
 * @param Integer[] $nums
 * @param Integer $k
 * @return Integer[]
 */
function resultsArray($nums, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
print_r(resultsArray([1, 2, 3, 4, 3, 2, 5], 3));  // Output: [3, 4, -1, -1, -1]
print_r(resultsArray([2, 2, 2, 2, 2], 4));  // Output: [-1, -1]
print_r(resultsArray([3, 2, 3, 2, 3, 2], 2));  // Output: [-1, 3, -1, 3, -1]
?>

説明：

• Sliding Window: i = 0 から i = n - k までの for ループを使用して、サイズ k のすべての部分配列を考慮します。各部分配列について、array_slice() を使用して部分配列を抽出します。
• 並べ替えチェック: 各部分配列について、部分配列を反復処理し、連続する要素の各ペアの差が 1 であるかどうかを確認することにより、連続する要素で並べ替えられているかどうかを確認します。
• 結果: 部分配列が有効な場合、部分配列の最大値が結果に追加されます。それ以外の場合は、-1 を追加します。

時間計算量:

• n - k 1 個の部分配列を反復処理します。
• 各部分配列について、要素が連続しているかどうかをチェックします。これには O(k) 時間がかかります。
• したがって、全体的な時間計算量は O((n - k 1) * k) となり、O(n * k) に単純化されます。

エッジケースの考慮事項:

• k = 1 の場合、すべての部分配列は自明にソートされ (要素が 1 つだけ含まれます)、各部分配列の累乗は要素自体になります。
• 部分配列が連続していない場合は、すぐに -1 を返します。

出力例:

1. nums = [1, 2, 3, 4, 3, 2, 5]、k = 3 の場合、出力は [3, 4, -1, -1, -1] です。
2. nums = [2, 2, 2, 2, 2]、k = 4 の場合、出力は [-1, -1] です。
3. nums = [3, 2, 3, 2, 3, 2]、k = 2 の場合、出力は [-1, 3, -1, 3, -1] です。

このソリューションは問題の制約に対して効率的に機能するはずです。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

---

1. サブ配列: サブ配列は、配列内の連続した空ではない要素のシーケンスです。 ↩

以上がK サイズの部分配列の検出力を求める Iの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。