判断数组是否可以排序-php教程-PHP中文网

Find if Array Can Be Sorted

3011。判断数组是否可以排序

难度：中等

主题：数组、位操作、排序

给你一个0索引数组，其中正整数nums。

在一次操作中，您可以交换任意两个相邻元素，如果它们具有相同个设置位¹。您可以执行此操作任意次（包括零）。

如果可以对数组进行排序，则返回 true，否则返回 false.

示例1：

输入： nums = [8,4,2,30,15]
输出： true
解释： 让我们看看每个元素的二进制表示。数字2、4和8分别具有一组二进制表示“10”、“100”和“1000”的位。数字15和30有四个设置位，每个设置位具有二进制表示“1111”和“11110”。我们可以使用 4 个操作对数组进行排序：
- 将 nums[0] 与 nums[1] 交换。此操作有效，因为 8 和 4 各有一个设置位。数组变为 [4,8,2,30,15].
- 将 nums[1] 与 nums[2] 交换。此操作有效，因为 8 和 2 各有一个设置位。数组变为 [4,2,8,30,15].
- 将 nums[0] 与 nums[1] 交换。该操作有效，因为 4 和 2 各有一个设置位。数组变为 [2,4,8,30,15].
- 将 nums[3] 与 nums[4] 交换。此操作有效，因为 30 和 15 各有四个设置位。数组变为 [2,4,8,15,30].
- 数组已排序，因此我们返回 true。
- 请注意，可能还有其他操作序列也对数组进行排序。

示例2：

输入： nums = [1,2,3,4,5]
输出： true
解释： 数组已经排序，因此我们返回 true。

示例 3：

输入： nums = [3,16,8,4,2]
输出： false
解释： 可以证明，不可能使用任意数量的操作对输入数组进行排序。

示例 4：

输入： nums = [75,34,30]
输出： false
解释： 可以证明，不可能使用任意数量的操作对输入数组进行排序。

约束：

提示：

将数组分割成段。每个段包含具有相同设置位数的连续元素。
从左到右，前一个段的最大元素应该小于当前段的最小元素。

解决方案：

我们需要确定是否可以通过仅交换二进制表示中具有相同数量的设置位的相邻元素来对数组进行排序。计划如下：

解决步骤：

关键观察：该操作允许我们仅在相邻元素具有相同数量的设置位数时交换它们。这限制了具有不同设置位数的元素之间的交换。
计划：
- 按二进制表示中设置的位数对元素进行分组。
- 单独对每个组进行排序，因为在一个组内，元素可以通过交换来重新排列。
- 对每个组进行排序后，将排序后的组重新合并在一起。
- 检查这个合并数组是否已排序。如果是，则可以使用允许的操作对数组进行排序。
步骤：
- 统计每个号码中的设定位数以及具有相同设定位数的组号码。
- 对每个组进行单独排序。
- 从这些已排序的组中重建数组并验证结果是否已排序。

让我们用 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
?>

登录后复制

解释：

countSetBits 函数：使用按位运算计算数字中设置的位数。
对元素进行分组：bitGroups 是一个关联数组，其中每个键代表设置的位数，每个值都是具有那么多设置位的数字数组。
排序和重建:
- 我们迭代 nums 以按设置的位数对元素进行分组。
- 我们对每个组进行独立排序。
- 然后，我们通过按其原始顺序插入每个已排序的组元素来重建数组。
- 最后，我们检查重建的数组是否按非降序排序。如果是，则返回true；否则，返回 false。
最终比较：将重建的数组与完全排序版本的 nums 进行比较。如果匹配，则返回true；否则，返回 false。