소인수 빼기 연산

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. 소수 생성(에라토스테네스의 체): 숫자(1000) 단위로 가능한 최대값까지 모든 소수 목록을 생성합니다.
2. 소수 빼기 연산: 숫자의 각 숫자에 대해 소수를 빼서 배열을 엄격하게 증가시킬 수 있는지 확인하세요.
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: 숫자로 각 요소를 반복하고 적절한 소수를 빼서 각 요소를 이전 요소보다 크게 만들 수 있는지 확인합니다.

   • $this->findLargestPrimeLessThan을 사용하여 num보다 작은 가장 큰 소수인 prevNum을 찾습니다.
   • 이러한 소수가 존재하는 경우 현재 숫자에서 이를 뺍니다.
   • 소수를 뺀 후 현재 숫자가 prevNum보다 크지 않으면 false를 반환합니다.
   • 그렇지 않으면 prevNum을 현재 숫자로 업데이트합니다.

2. sieveEratosthenes: 에라토스테네스의 체를 사용하여 최대 1000까지의 모든 소수를 생성하고 배열로 반환합니다.

3. findLargestPrimeLessThan: 이진 검색을 사용하여 주어진 한계보다 작은 가장 큰 소수를 찾아 뺄셈을 위한 최적의 소수를 찾습니다.

복잡성 분석

• 시간 복잡도: O(n . √m), 여기서 n은 숫자와 m의 길이입니다. 은 요소의 최대값(여기서는 m = 1000)입니다.
• 공간 복잡도: O(m), 최대 1000까지의 소수 목록을 저장하는 데 사용됩니다.

이 솔루션은 설명된 소수 빼기 연산을 수행하여 숫자를 엄격하게 증가시킬 수 있는지 여부에 따라 true 또는 false를 반환합니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.

• 링크드인
• 깃허브

위 내용은 소인수 빼기 연산의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!