スペシャルアレイ II

3152。スペシャルアレイ II

難易度: 中

トピック: 配列、二分探索、接頭辞合計

隣接する要素のすべてのペアに異なるパリティを持つ 2 つの数値が含まれている場合、配列は 特別とみなされます。

整数の配列と 2D 整数行列のクエリが与えられます。クエリ[i] = [from_i, to_i] の場合、あなたのタスクはそれをチェックすることです。部分配列¹ nums[from_i..to_i] は特別かどうか。

nums[fromi_..toi_{] が特別な場合に、answer[i] が true となるようなブール値の配列を返します}。

例 1:

• 入力: 数値 = [3,4,1,2,6]、クエリ = [[0,4]]
• 出力: [false]
• 説明: 部分配列は [3,4,1,2,6] です。 2 と 6 は両方とも偶数です。

例 2:

• 入力: 数値 = [4,3,1,6]、クエリ = [[0,2],[2,3]]
• 出力: [false,true]
• 説明:

部分配列は [4,3,1] です。 3と1はどちらも奇数です。したがって、このクエリに対する答えは false です。
部分配列は [1,6] です。 (1,6) のペアは 1 つだけあり、これには異なるパリティを持つ数値が含まれています。したがって、このクエリに対する答えは true です。

制約:

1 5 1 5 1 5 クエリ[i].length == 2
0

ヒント:

配列を、交差しない連続した特殊な部分配列に分割してみます。
各クエリについて、そのクエリの最初と最後の要素が同じサブ配列内にあるかどうかを確認します。

解決策:

nums の部分配列が「特別」であるかどうかを判断する必要があります。つまり、部分配列内の隣接する要素のすべてのペアが異なるパリティを持つ必要があります (1 つは奇数で、もう 1 つは偶数である必要があります)。

アプローチ：

1. パリティ遷移の特定: 配列を前処理して、パリティが変更される位置をマークできます。例えば：
   0 は偶数を表します。
   1 は奇数を表します。

そのアイデアは、隣接する要素が異なるパリティを持つすべての位置を識別することです。これは、クエリ内の位置が同じ「特別な」ブロックの一部であるかどうかをチェックすることで、サブ配列が特別であるかどうかを効率的に判断するのに役立ちます。

1. 前処理: バイナリ配列 parity_change を作成します。隣接する要素のパリティが異なる場合は各要素が 1、それ以外の場合は 0 になります。例:
   

   • 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]
?>

説明：

1. パリティ遷移の前処理:
   要素 nums[i] と nums[i 1] のパリティが異なる場合、parity_change[i] = 1 を計算します。それ以外の場合は、0 に設定します。

2. プレフィックス合計配列:
   prefix_sum[i] には、配列の先頭からインデックス i までのパリティ遷移の累積数が格納されます。これにより、次の式を使用して、一定時間内に任意の部分配列 [from, to] で発生した遷移の数を計算できます。
   

   $transition_count = $prefix_sum[$to] - $prefix_sum[$from];

1. クエリ評価: 各クエリについて、遷移の数が部分配列の長さから 1 を引いたものに等しい場合、その部分配列は特別であるため、true を返します。それ以外の場合は false を返します。

時間計算量:

• パリティ遷移の前処理には O(n) かかります。
• プレフィックス合計配列の構築には O(n) かかります。
• 各クエリは、プレフィックス合計配列を使用して O(1) で答えることができます。
• したがって、合計の時間計算量は O(n q) です。ここで、n は配列の長さ、q はクエリの数です。

このソリューションは、最適化されたアプローチで問題の制約を効率的に処理します。

連絡先リンク

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

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

• LinkedIn
• GitHub

---

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

以上がスペシャルアレイ IIの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。