排序排列【力扣LeetCode & 每日一题】

排序排列

网页链接

力扣LeetCode

力扣LeetCode & 每日一题，完成每日打卡，即可获得力扣积分。获得相应数量的积分，能在【力扣商店】，换取相应奖品！助力每日有题做，丰盈积分日益多！

---

题目描述

给你一个长度为 $n$ 的整数数组 nums，其中 nums 是范围 [0..n - 1] 内所有数字的一个 排列。

你可以在满足条件 nums[i] AND nums[j] == k 的情况下交换下标 $i$ 和 $j$ 的元素，其中 AND 表示按位与操作，$k$ 是一个非负整数。

返回可以使数组按 非递减 顺序排序的最大值 $k$（允许进行任意次这样的交换）。如果 nums 已经是已排序的，返回 0。

排列 是数组所有元素的一种重新排列。

---

输入描述

一个长度为 $n$ 的整数数组 nums，它是范围 [0..n - 1] 内所有数字的一个排列。

---

输出描述

返回可以使数组按非递减顺序排序的最大值 $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\le n==\text{nums.length}\le 10^5$
• $0\le \text{nums}[i]\le n-1$
• nums 是从 $0$ 到 $n-1$ 的一个排列

解题思路

本题是按位与上界 + 交换图连通性问题。给定排列 nums，允许在下标 $i,j$ 上交换元素，当且仅当当前两个值满足 nums[i] & nums[j] == k。要求能够通过任意次交换把数组排成递增排列，求最大的 $k$。

1. 错位元素

若 nums[i] != i，说明位置 $i$ 上的值 nums[i] 最终必须离开该位置，因此它一定需要参与至少一次交换。记所有错位位置上的值为集合：
M = {   n u m s [ i ] ∣ n u m s [ i ] ≠ i   } M = \{\, nums[i] \mid nums[i] \ne i \,\} M={nums[i]∣nums[i]=i}
若 $M$ 为空，说明数组已经有序，直接返回 0。

2. 上界：$k$ 必须是所有错位值的位子集

对于任意错位值 $x\in M$，它必须通过某次交换移动。若它和某个值 $y$ 交换，则必须满足：
$$x\&y=k$$
按位与的结果一定是 $x$ 的子集，因此：
$$(k\&x)=k$$
即 $k$ 的所有二进制位都必须包含在 $x$ 中。由于这对所有错位值 $x\in M$ 都成立，所以：
$$k\subseteq \underset{x\in M}{\bigwedge }x$$
也就是说，$k$ 不能超过所有错位值的按位与。令：
$$R=\underset{x\in M}{\bigwedge }x$$
则任何可行方案都满足 $k$ 是 $R$ 的位子集，因此最大值不会超过 $R$。

3. 充分性：$k=R$ 一定可行

由于所有元素都在 $[0,n-1]$ 内，而 $R$ 是若干小于 $n$ 的数的按位与，所以 $R<n$，且 $R$ 本身也是排列中的一个值。

对于任意错位值 $x\in M$，由 $R$ 的定义有：
$$x\&R=R$$
因此 $x$ 与值 $R$ 交换时，按位与恰好等于 $R$，满足条件。

• 若 $R$ 本身也是错位值，则可以把 $R$ 作为枢纽，将所有错位值通过它与 $R$ 的交换重新排列到正确位置；
• 若 $R$ 已经就位，即位置 $R$ 上就是值 $R$，则把 $R$ 当作临时缓冲，先将需要移动的元素与 $R$ 交换，最后再把 $R$ 换回位置 $R$。

因此所有错位元素都可以被正确归位，且不会破坏已经就位的元素。所以 $k=R$ 一定可行。

综上，最大可行的 $k$ 就是所有错位值的按位与：
$$\boxed{k=\underset{nums[i]\ne i}{\bigwedge }nums[i]}$$

4. 代码实现

代码中：

• r 初始为 -1，二进制全为 $1$，作为按位与的单位元；
• 遍历数组，若 i != a[i]，则令 r &= a[i]；
• 若没有错位元素，r 仍为 -1，最后通过 max(r, 0) 返回 0；
• 否则 r 就是所有错位值的按位与，即最大可行的 $k$。

5. 复杂度分析

• 时间复杂度：$O(n)$，只需一次线性扫描；
• 空间复杂度：$O(1)$，只使用常数个变量。

总结

每个错位元素都必须参与交换，因此 $k$ 必须是每个错位值的位子集，这给出上界 $R=\text{AND}$ 所有错位值。又因为 $R$ 本身存在于排列中，且与任意错位值 $x$ 满足 x & R == R，所以可以用 $R$ 作为枢纽完成所有错位元素的归位。因此最大 $k$ 就是所有错位值的按位与；若数组已经有序则答案为 0。

代码内容

class Solution {
public:
    int sortPermutation(vector<int>& a) {
        int r = -1;
        for (int i = 0; i < a.size(); i++) {
            int x = a[i];
            if (i != x) {
                r &= x;
            }
        }
        return max(r, 0);
    }
};

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/2301_80065123/article/details/168859479