配列がソートできるかどうかを調べる

3011。配列がソートできるかどうかを調べる

難易度: 中

トピック: 配列、ビット操作、ソート

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

1 つの 操作で、同じ数の設定ビット1がある場合、任意の 2 つの^隣接要素を交換できます。この操作は任意回（ゼロを含む）行うことができます。

配列をソートできる場合は true を返し、それ以外の場合は falseを返します。

例 1:

• 入力: 数値 = [8,4,2,30,15]
• 出力: true
• 説明: すべての要素のバイナリ表現を見てみましょう。数値 2、4、および 8 には、それぞれ 2 進表現「10」、「100」、および「1000」を持つ 1 つのセット ビットがあります。数値 15 と 30 には 4 つのセット ビットがあり、それぞれバイナリ表現「1111」と「11110」を持ちます。 4 つの操作を使用して配列を並べ替えることができます。
  • nums[0] を nums[1] と交換します。 8 と 4 にはそれぞれ 1 つのセットビットがあるため、この操作は有効です。配列は [4,8,2,30,15] になります。
  • nums[1] を nums[2] と交換します。 8 と 2 にはそれぞれ 1 つのセットビットがあるため、この操作は有効です。配列は [4,2,8,30,15] になります。
  • nums[0] を nums[1] と交換します。 4 と 2 にはそれぞれ 1 つのセットビットがあるため、この操作は有効です。配列は [2,4,8,30,15] になります。
  • nums[3] を nums[4] と交換します。 30 と 15 にはそれぞれ 4 つの設定ビットがあるため、この操作は有効です。配列は [2,4,8,15,30] になります。
  • 配列はソートされているため、true を返します。
  • 配列を並べ替える他の一連の操作も存在する可能性があることに注意してください。

例 2:

• 入力: 数値 = [1,2,3,4,5]
• 出力: true
• 説明: 配列はすでにソートされているため、true を返します。

例 3:

• 入力: 数値 = [3,16,8,4,2]
• 出力: false
• 説明: 任意の数の演算を使用して入力配列を並べ替えることはできないことがわかります。

例 4:

• 入力: 数値 = [75,34,30]
• 出力: false
• 説明: 任意の数の演算を使用して入力配列を並べ替えることはできないことがわかります。

制約:

• 1
• 1 8

ヒント:

1. 配列をセグメントに分割します。各セグメントには、同じ数の設定ビットを持つ連続した要素が含まれます。
2. 左から右に、前のセグメントの最大の要素は現在のセグメントの最小の要素より小さくなければなりません。

解決策:

バイナリ表現で同じ数の設定ビットを持つ隣接する要素を交換するだけで配列をソートできるかどうかを判断する必要があります。計画は次のとおりです:

解決策の手順:

1. Key Observation: この操作により、設定されたビット数が同じである場合にのみ、隣接する要素を交換できます。これにより、設定ビット数が異なる要素間でのスワップが制限されます。

2. 計画:

   • バイナリ表現で設定されたビット数で要素をグループ化します。
   • グループ内では要素を入れ替えることで再配置できるため、各グループを個別に並べ替えます。
   • 各グループを並べ替えた後、並べ替えたグループを元にマージします。
   • このマージされた配列がソートされているかどうかを確認します。そうであれば、許可された操作を使用して配列を並べ替えることが可能です。

3. ステップ:

   • 各数値の設定ビット数をカウントし、同じ設定ビット数の番号をグループ化します。
   • 各グループを個別に並べ替えます。
   • これらの並べ替えられたグループから配列を再構築し、結果が並べ替えられているかどうかを確認します。

このソリューションを PHP で実装してみましょう: 3011。配列がソートできるかどうかを調べる

<?php
/**
 * Helper function to count set bits in a number
 *
 * @param $n
 * @return int
 */
function countSetBits($n) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

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

// Test cases
$nums1 = [8, 4, 2, 30, 15];
$nums2 = [1, 2, 3, 4, 5];
$nums3 = [3, 16, 8, 4, 2];
$nums4 = [75, 34, 30];

echo canBeSorted($nums1) ? 'true' : 'false'; // Expected output: true
echo "\n";
echo canBeSorted($nums2) ? 'true' : 'false'; // Expected output: true
echo "\n";
echo canBeSorted($nums3) ? 'true' : 'false'; // Expected output: false
echo "\n";
echo canBeSorted($nums4) ? 'true' : 'false'; // Expected output: false
?>

説明：

1. countSetBits 関数: ビット単位の演算を使用して、数値内の設定ビット数をカウントします。
2. グループ化要素: bitGroups は連想配列であり、各キーは設定されたビット数を表し、各値はその多くの設定されたビットを含む数値の配列です。

3. 並べ替えと再構築:

   • 数値を反復処理して、設定されたビット数で要素をグループ化します。
   • 各グループを個別に並べ替えます。
   • 次に、ソートされた各グループ要素を元の順序で挿入して配列を再構築します。
   • 最後に、再構築された配列が非降順でソートされているかどうかを確認します。そうである場合は、true を返します。それ以外の場合は false を返します。

4. 最終比較: 再構築された配列を完全にソートされたバージョンの nums と比較します。一致する場合は true を返します。それ以外の場合は false を返します。

複雑さの分析

• 時間計算量: 各グループ内での並べ替えと最終比較による O(n log n)。
• 空間複雑度: ビット グループを格納するための O(n)。

このソリューションでは、同じ設定ビット数を持つ隣接する要素のみを交換し、可能であれば並べ替え順序を実現します。

連絡先リンク

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

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

• LinkedIn
• GitHub

---

1. セット ビット セット ビットとは、値 1 を持つ数値の 2 進表現内のビットを指します。 ↩

以上が配列がソートできるかどうかを調べるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。