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

🟠 🔖 位运算 数组 排序 🔗 力扣open in new window LeetCodeopen in new window

题目

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 returnfalse.

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 <= nums.length <= 100
1 <= nums[i] <= 28

解题思路

首先计算数组 nums 中每个数字的二进制表示中“1”的个数（即设置位的数量），并将每个数字的设置位数存储在一个数组 bitCounts 中。
由于只能交换相邻的元素，需要将具有相同设置位数量的相邻元素视为一个连续的“子数组”，并对子数组进行单独排序。
通过上述分组排序，拼接成一个新的数组，逐项检查是否是非降序排列。如果是，则返回 true；否则返回 false。

复杂度分析

时间复杂度：O(n log n)，其中 n 为 nums 的长度，每个相同设置位数的分组排序所需的复杂度为 O(n log n)。
空间复杂度：O(n)，用于存储每个数字的设置位数。

代码

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canSortArray = function (nums) {
	// 计算每个数字的设置位数
	const bitCount = nums.map((num) => num.toString(2).split('1').length - 1);

	// 将 nums 中相邻相同设置位数的元素按组进行排序
	let i = 0;
	while (i < nums.length) {
		let j = i;

		// 找出相同设置位数的连续子数组
		while (j < nums.length && bitCount[i] == bitCount[j]) {
			j++;
		}

		// 对该子数组进行排序
		nums = [
			...nums.slice(0, i),
			...nums.slice(i, j).sort((a, b) => a - b),
			...nums.slice(j)
		];

		// 更新 i 为 j 继续检查下一个分组
		i = j;
	}

	// 检查排序后的 nums 是否是非降序的
	for (let i = 1; i < nums.length; i++) {
		if (nums[i] < nums[i - 1]) {
			return false;
		}
	}
	return true;
};

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

# 3011. 判断一个数组是否可以变为有序

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

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

题目

题目大意

解题思路

复杂度分析

代码

相关题目