素数減算演算

2601。素数減算演算

難易度: 中

トピック: 配列、数学、二分探索、貪欲、整数論

長さ n の 0 インデックス 整数配列 nums が与えられます。

次の操作は何度でも実行できます:

• これまでに選択したことのないインデックス i を選択し、厳密に nums[i] より小さい素数 p を選択し、nums[i] から p を減算します。

上記の操作を使用して nums を厳密に増加する配列にできる場合は true を返し、それ以外の場合は falseを返します。

厳密に増加する配列は、各要素がその前の要素より厳密に大きい配列です。

例 1:

• 入力: 数値 = [4,9,6,10]
• 出力: true
• 説明: 最初の操作: i = 0 および p = 3 を選択し、nums[0] から 3 を引くと、nums は [1,9,6,10] になります。
  • 2 番目の演算: i = 1、p = 7 では、nums[1] から 7 を減算し、nums は [1,2,6,10] と等しくなります。
  • 2 番目の操作の後、nums は厳密に昇順にソートされるため、答えは true になります。

例 2:

• 入力: 数値 = [6,8,11,12]
• 出力: true
• 説明: 当初、nums は厳密に昇順にソートされるため、操作を行う必要はありません。

例 3:

• 入力: 数値 = [5,8,3]
• 出力: false
• 説明: 数値を厳密に昇順にソートする操作を実行する方法がないことが証明できるため、答えは false です。

制約:

• 1
• 1
• nums.length == n

ヒント:

1. nums[i] から減算する素数がたくさんあるかどうかを考えてみましょう。どの素数がより最適ですか?
2. nums[i] から減算するのに最も最適な素数は、nums[i] を可能な限り小さくし、nums[i-1] より大きくする素数です。

解決策:

アルゴリズムを分解し、PHP の構文と機能に適応させる必要があります。この解決策には主に次の手順が含まれます:

1. 素数の生成 (エラトステネスの篩): nums で可能な最大値 (1000) までのすべての素数のリストを生成します。
2. 素数減算演算: nums の各数値について、配列を厳密に増加させるために素数を減算できるかどうかを確認します。
3. 素数の二分検索: 二分検索を使用して、シーケンスを厳密に増加させ続ける現在の数より小さい最大の素数を見つけます。

このソリューションを PHP で実装してみましょう: 2601。素数減算演算

<?php
class Solution {

    /**
     * @param Integer[] $nums
     * @return Boolean
     */
    function primeSubOperation($nums) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * Helper function to generate all primes up to n using Sieve of Eratosthenes
     *
     * @param $n
     * @return array
     */
    private function sieveEratosthenes($n) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * Helper function to find the largest prime less than a given limit using binary search
     *
     * @param $primes
     * @param $limit
     * @return mixed|null
     */
    private function findLargestPrimeLessThan($primes, $limit) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }
}

// Example usage:
$solution = new Solution();
echo $solution->primeSubOperation([4, 9, 6, 10]) ? 'true' : 'false';  // Output: true
echo $solution->primeSubOperation([6, 8, 11, 12]) ? 'true' : 'false'; // Output: true
echo $solution->primeSubOperation([5, 8, 3]) ? 'true' : 'false';      // Output: false
?>

説明：

1. primeSubOperation: nums 内の各要素をループし、適切な素数を減算することで各要素を前の要素より大きくできるかどうかを確認します。

   • $this->findLargestPrimeLessThan を使用して、num - prevNum 未満の最大の素数を見つけます。
   • そのような素数が存在する場合、現在の数値からそれを減算します。
   • 素数を減算した後、現在の数値が prevNum より大きくない場合は、false を返します。
   • それ以外の場合は、prevNum を現在の数値に更新します。

2. sieveEratosthenes: エラトステネスのふるいを使用して 1000 までのすべての素数を生成し、配列として返します。

3. findLargestPrimeLessThan: 二分探索を使用して、指定された制限未満の最大の素数を検索し、減算に最適な素数を確実に見つけます。

複雑さの分析

• 時間計算量: O(n . √m)、n は nums と m の長さです。 nums 単位の要素の最大値です (ここでは m = 1000).
• 空間複雑度: O(m)、最大 1000 の素数のリストを保存するために使用されます。

この解決策は、説明されている素数減算演算を実行することで nums を厳密に増加させることが可能かどうかに基づいて true または false を返します。

連絡先リンク

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

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

• LinkedIn
• GitHub

以上が素数減算演算の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。