[LeetCode] 3011. Find if Array Can Be Sorted

In one operation, you can swap any two adjacent elements if they have the same number of set bits. You are allowed to do this operation any number of times (including zero).

Return true if you can sort the array, else return false.

Example 1:
Input: nums = [8,4,2,30,15]
Output: true
Explanation: Let’s look at the binary representation of every element. The numbers 2, 4, and 8 have one set bit each with binary representation “10”, “100”, and “1000” respectively. The numbers 15 and 30 have four set bits each with binary representation “1111” and “11110”.
We can sort the array using 4 operations:

• Swap nums[0] with nums[1]. This operation is valid because 8 and 4 have one set bit each. The array becomes [4,8,2,30,15].
• Swap nums[1] with nums[2]. This operation is valid because 8 and 2 have one set bit each. The array becomes [4,2,8,30,15].
• Swap nums[0] with nums[1]. This operation is valid because 4 and 2 have one set bit each. The array becomes [2,4,8,30,15].
• Swap nums[3] with nums[4]. This operation is valid because 30 and 15 have four set bits each. The array becomes [2,4,8,15,30].
  The array has become sorted, hence we return true.
  Note that there may be other sequences of operations which also sort the array.

Example 2:
Input: nums = [1,2,3,4,5]
Output: true
Explanation: The array is already sorted, hence we return true.

Example 3:
Input: nums = [3,16,8,4,2]
Output: false
Explanation: It can be shown that it is not possible to sort the input array using any number of operations.

Constraints:
1 <= nums.length <= 100
1 <= nums[i] <= 28

判断一个数组是否可以变为有序。

给你一个下标从 0 开始且全是 正 整数的数组 nums 。

一次 操作 中，如果两个 相邻 元素在二进制下设置位的数目 相同 ，那么你可以将这两个元素交换。你可以执行这个操作 任意次 （也可以 0 次）。

如果你可以使数组变为非降序，请你返回 true ，否则返回 false 。

示例 1：
输入：nums = [8,4,2,30,15]
输出：true
解释：我们先观察每个元素的二进制表示。 2 ，4 和 8 分别都只有一个数位为 1 ，分别为 “10” ，”100” 和 “1000” 。15 和 30 分别有 4 个数位为 1 ：”1111” 和 “11110” 。
我们可以通过 4 个操作使数组非降序：

• 交换 nums[0] 和 nums[1] 。8 和 4 分别只有 1 个数位为 1 。数组变为 [4,8,2,30,15] 。
• 交换 nums[1] 和 nums[2] 。8 和 2 分别只有 1 个数位为 1 。数组变为 [4,2,8,30,15] 。
• 交换 nums[0] 和 nums[1] 。4 和 2 分别只有 1 个数位为 1 。数组变为 [2,4,8,30,15] 。
• 交换 nums[3] 和 nums[4] 。30 和 15 分别有 4 个数位为 1 ，数组变为 [2,4,8,15,30] 。
  数组变成有序的，所以我们返回 true 。
  注意我们还可以通过其他的操作序列使数组变得有序。

示例 2：
输入：nums = [1,2,3,4,5]
输出：true
解释：数组已经是非降序的，所以我们返回 true 。

示例 3：
输入：nums = [3,16,8,4,2]
输出：false
解释：无法通过操作使数组变为非降序。

思路

这是一道关于二进制的题目。注意元素在二进制下设置位的数目相同这个定义的意思其实就是两个数字的二进制表示中的 1 的个数要相同。如果两个数字的 1 的个数相同，且他们在原数组里是相邻元素，才能互相交换位置。

所以我们需要遍历 input 数组，看一看每个数字的 Integer.bitCount(num)，如果某一串连续的数字他们的 1 的个数都相同的话，这一段数字就可以互相交换以确保他们有序。所以数组会因为 1 的个数的不同而变得分段有序。

再次遍历排过序的数组，如果分段排序不能导致最后的整体有序，则返回 false，否则返回 true。

复杂度

时间O(nlogn)
空间O(1)

代码

Java实现

class Solution {
    public boolean canSortArray(int[] nums) {
        // corner case
        if (nums == null || nums.length == 0) {
            return true;
        }

        // normal case
        int n = nums.length;
        int i = 0;
        while (i < n) {
            int start = i;
			// 二进制表达里 1 的个数
            int ones = Integer.bitCount(nums[i]);
            while (i < n && Integer.bitCount(nums[i]) == ones) {
                i++;
            }
			// 分段排序
            Arrays.sort(nums, start, i);
        }

        for (int j = 1; j < n; j++) {
            if (nums[j] < nums[j - 1]) {
                return false;
            }
        }
        return true;
    }
}