Medium
题目描述
给你一个长度为 n 的整数数组 nums，其中 nums 是范围 [0..n-1] 中数字的一个排列。
你只能在满足 nums[i] AND nums[j] == k 的情况下交换索引 i 和 j 处的元素，其中 AND 表示按位与运算，k 是一个非负整数。
返回使数组能够通过任意次数的此类交换按非递减顺序排序的 k 的最大值。如果 nums 已经排序，则返回 0。
示例 1：
输入：nums = [0,3,2,1]
输出：1
解释：选择 k = 1。交换 nums[1] = 3 和 nums[3] = 1 是允许的，因为 nums[1] AND nums[3] == 1，结果得到排序后的排列：[0, 1, 2, 3]。
示例 2：
输入：nums = [0,1,3,2]
输出：2
解释：选择 k = 2。交换 nums[2] = 3 和 nums[3] = 2 是允许的，因为 nums[2] AND nums[3] == 2，结果得到排序后的排列：[0, 1, 2, 3]。
示例 3：
输入：nums = [3,2,1,0]
输出：0
解释：只有 k = 0 允许排序，因为没有更大的 k 允许满足 nums[i] AND nums[j] == k 的必需交换。
约束条件：
- 1 <= n == nums.length <= 10^5
- 0 <= nums[i] <= n - 1
- nums 是从 0 到 n-1 整数的排列
提示：
- 对所有不在正确位置的元素进行按位与运算。
解题思路
这道题的关键在于理解什么时候两个元素可以交换，以及如何找到最大的k值。
核心思路：
- 如果数组已经排序（即每个元素都在正确位置 nums[i] == i），返回0
- 否则，找出所有不在正确位置的元素
- 对于能够排序的k值，所有不在正确位置的元素都必须能够通过满足按位与条件的交换到达正确位置
- 关键观察：如果存在一个k值使得数组可以排序，那么所有不在正确位置的元素的按位与结果必须包含k的所有位
算法步骤：
- 检查数组是否已排序，如果是则返回0
- 找出所有不在正确位置的元素
- 计算这些元素的按位与结果，这就是答案
- 这是因为如果要通过交换使数组排序，所有需要移动的元素都必须能够相互交换，而相互交换的条件是它们的按位与等于k
为什么这样做是正确的：
- 如果两个元素都不在正确位置，且它们的按位与为k，那么它们可以交换
- 为了使整个数组排序，所有不在正确位置的元素都需要能够找到交换路径
- 通过并查集的思想，如果所有错位元素都有共同的按位与模式，它们就能形成连通分量进行交换
代码实现
class Solution {
public:
int sortPermutation(vector<int>& nums) {
int n = nums.size();
int result = (1 << 20) - 1; // 初始化为所有位都是1
bool needSort = false;
for (int i = 0; i < n; i++) {
if (nums[i] != i) {
needSort = true;
result &= nums[i];
}
}
return needSort ? result : 0;
}
};
class Solution:
def sortPermutation(self, nums: List[int]) -> int:
result = (1 << 20) - 1 # 初始化为所有位都是1
need_sort = False
for i, num in enumerate(nums):
if num != i:
need_sort = True
result &= num
return result if need_sort else 0
public class Solution {
public int SortPermutation(int[] nums) {
int n = nums.Length;
int result = (1 << 20) - 1; // 初始化为所有位都是1
bool needSort = false;
for (int i = 0; i < n; i++) {
if (nums[i] != i) {
needSort = true;
result &= nums[i];
}
}
return needSort ? result : 0;
}
}
var sortPermutation = function(nums) {
let result = (1 << 20) - 1; // 初始化为所有位都是1
let needSort = false;
for (let i = 0; i < nums.length; i++) {
if (nums[i] !== i) {
needSort = true;
result &= nums[i];
}
}
return needSort ? result : 0;
};
复杂度分析
| 复杂度类型 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n) | 只需要遍历数组一次 |
| 空间复杂度 | O(1) | 只使用常数额外空间 |