소수 빼기 연산

2601. 소인수 빼기 연산

난이도:중

주제: 배열, 수학, 이진 검색, 탐욕, 정수론

길이가 n인 인덱스가 0인 정수 배열이 제공됩니다.

다음 작업은 원하는 만큼 여러 번 수행할 수 있습니다.

• 이전에 선택하지 않은 인덱스 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]이 됩니다.
  • 두 번째 연산: i = 1, p = 7, nums[1]에서 7을 빼면 nums는 [1,2,6,10]이 됩니다.
  • 두 번째 연산 후 nums는 순차 오름차순으로 정렬되므로 답은 참입니다.

예 2:

• 입력: 숫자 = [6,8,11,12]
• 출력: true
• 설명: 처음에 nums는 엄격하게 오름차순으로 정렬되므로 아무런 작업도 수행할 필요가 없습니다.

예 3:

• 입력: 숫자 = [5,8,3]
• 출력: 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!