특수 배열 II

3152. 특수 배열 II

난이도:중

주제: 배열, 이진 검색, 접두사 합

인접한 요소의 모든 쌍에 패리티가 다른 두 개의 숫자가 포함된 경우 배열은 특별한 것으로 간주됩니다.

정수 숫자 배열과 2D 정수 행렬 쿼리가 제공됩니다. 여기서 쿼리[i] = [from_i, to_i]에 대해 작업은 다음을 확인하는 것입니다. 하위 배열¹ nums[from_i..to_i]는 특별하거나 그렇지 않습니다.

반환nums[from_i..to_i]이 특별인 경우 응답[i]이 참이 되도록 부울 응답 배열을 반환합니다.

예 1:

• 입력: 숫자 = [3,4,1,2,6], 쿼리 = [[0,4]]
• 출력: [거짓]
• 설명: 하위 배열은 [3,4,1,2,6]입니다. 2와 6은 모두 짝수입니다.

예 2:

• 입력: 숫자 = [4,3,1,6], 쿼리 = [[0,2],[2,3]]
• 출력: [false,true]
• 설명:

1. 하위 배열은 [4,3,1]입니다. 3과 1은 모두 홀수입니다. 따라서 이 쿼리에 대한 답변은 거짓입니다.
2. 하위 배열은 [1,6]입니다. 단 하나의 쌍(1,6)이 있으며 여기에는 패리티가 다른 숫자가 포함됩니다. 따라서 이 쿼리에 대한 답변은 사실입니다.

제약조건:

• 1 <= nums.length <= 10⁵
• 1 <= 숫자[i] <= 10⁵
• 1 <= query.length <= 10⁵
• 쿼리[i].length == 2
• 0 <= 쿼리[i][0] <= 쿼리[i][1] <= nums.length - 1

힌트:

1. 배열을 교차하지 않는 연속적인 특수 하위 배열로 분할해 보세요.
2. 각 쿼리에 대해 해당 쿼리의 첫 번째 요소와 마지막 요소가 동일한 하위 배열에 있는지 확인하세요.

해결책:

숫자의 하위 배열이 "특별"한지 여부를 확인해야 합니다. 즉, 하위 배열에 있는 인접한 요소의 모든 쌍은 서로 다른 패리티를 가져야 합니다(하나는 홀수여야 하고 다른 하나는 짝수여야 함).

접근하다:

1. 패리티 전환 식별: 패리티가 변경되는 위치를 표시하기 위해 배열을 전처리할 수 있습니다. 예를 들어:
   • 0은 짝수를 나타냅니다.
   • 1은 홀수를 나타냅니다.

인접한 요소가 서로 다른 패리티를 갖는 모든 위치를 식별하는 것이 아이디어입니다. 이는 쿼리의 위치가 동일한 "특수" 블록의 일부인지 확인하여 하위 배열이 특수한지 효율적으로 결정하는 데 도움이 됩니다.

1. 전처리:
   인접한 요소가 서로 다른 패리티를 가지면 각 요소가 1이고, 그렇지 않으면 0인 이진 배열 parity_change를 만듭니다. 예를 들면 다음과 같습니다.

   • nums[i]와 nums[i 1]의 패리티가 다른 경우 parity_change[i] = 1로 설정하고, 그렇지 않으면 0으로 설정합니다.

2. 접두사 합계 배열:
   인덱스 i의 각 항목이 해당 인덱스까지의 누적 패리티 전환 수를 나타내는 접두사 합계 배열 prefix_sum을 구성합니다. 이는 하위 배열 내의 모든 쌍이 서로 다른 패리티를 가지고 있는지 빠르게 확인하는 데 도움이 됩니다.

3. 쿼리 처리:
   각 쿼리 [from, to]에 대해 [from, to-1] 범위에서 패리티가 변경되지 않는 위치가 있는지 확인합니다. 이는 접두사 합계 값의 차이를 확인하여 수행할 수 있습니다: prefix_sum[to] - prefix_sum[from].

이 솔루션을 PHP로 구현해 보겠습니다: 3152. 특수 배열 II

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

// Example usage
$nums1 = [3,4,1,2,6];
$queries1 = [[0, 4]];
print_r(specialArray($nums1, $queries1)); // [false]

$nums2 = [4,3,1,6];
$queries2 = [[0, 2], [2, 3]];
print_r(specialArray($nums2, $queries2)); // [false, true]
?>




<h3>
  
  
  설명:
</h3>

<ol>
<li><p><strong>패리티 전환 전처리:</strong><br>
nums[i]와 nums[i 1] 요소가 서로 다른 패리티를 갖는 경우 parity_change[i] = 1을 계산합니다. 그렇지 않으면 0으로 설정합니다.</p></li>
<li><p><strong>접두사 합계 배열:</strong><br>
prefix_sum[i]는 배열 시작부터 인덱스 i까지 패리티 전환의 누적 횟수를 저장합니다. 이를 통해 다음 공식을 사용하여 일정 시간 동안 하위 배열 [from, to]에서 발생한 전환 수를 계산할 수 있습니다.<br>
</p></li>
</ol>

<pre class="brush:php;toolbar:false">   $transition_count = $prefix_sum[$to] - $prefix_sum[$from];

1. 쿼리 평가: 각 쿼리에 대해 전환 횟수가 하위 배열의 길이에서 1을 뺀 것과 같으면 해당 하위 배열은 특별하므로 true를 반환합니다. 그렇지 않으면 false를 반환합니다.

시간 복잡도:

• 패리티 전환을 전처리하는 데 O(n)이 걸립니다.
• 접두사 합계 배열을 구성하는 데는 O(n)이 소요됩니다.
• 각 쿼리는 접두사 합계 배열을 사용하여 O(1)로 응답할 수 있습니다.
• 따라서 총 시간 복잡도는 O(n q)입니다. 여기서 n은 배열의 길이이고 q는 쿼리 수입니다.

이 솔루션은 최적화된 접근 방식으로 문제 제약 조건을 효율적으로 처리합니다.

연락처 링크

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

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

• 링크드인
• 깃허브

---

1. 하위 배열 하위 배열은 배열 내 연속된 요소 시퀀스입니다. ↩

위 내용은 특수 배열 II의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!