判断一个数组是否可以变为有序
难度:
标签:
题目描述
You are given a 0-indexed array of positive integers nums.
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 <= 1001 <= nums[i] <= 28
代码结果
运行时间: 26 ms, 内存: 16.0 MB
/*
* 题目思路：
* 通过Java Stream API计算每个元素的二进制1的数量，并检查这些数量的顺序能否通过相邻交换变为升序。
*/
import java.util.Arrays;
public class Solution {
public boolean canBeSorted(int[] nums) {
int[] bitCounts = Arrays.stream(nums)
.map(Integer::bitCount)
.toArray();
return Arrays.equals(bitCounts, Arrays.stream(bitCounts).sorted().toArray());
}
}解释
方法:
题解的核心思路是首先按照数字二进制中1的个数将数组分组，然后对每个组内的元素进行排序。每个分组的元素在二进制中有相同数量的1，因此这些元素可以任意交换位置。如果按1的数量排序后的每个分组内的数值顺序可以连接起来形成一个有序序列，则返回true。否则，若有任何一个组的最小值小于前一个组的最大值，则返回false。
时间复杂度:
O(n log n)
空间复杂度:
O(n)
代码细节讲解
🦆
在算法中，如何保证按照二进制中1的个数对数组元素进行分组的正确性？
▷🦆
在对每个分组进行排序后，为什么可以直接比较分组间的元素而不是继续比较分组内的所有元素？
▷🦆
在实现中，如果连续两个分组的最小和最大值相等，这会影响算法的输出结果吗？
▷