排序排列

题目内容

给你一个长度为 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]。

注

更多完整用例查看官方题目

解题思路

首先，理解题意，数组由 $[0, n-1]$ 内的所有整数组成的拥有 $n$ 个元素的数组，数组处于一无序状态，目标是变成一个升序的数组，

排序的过程是通过两两元素交换后得来。排序过程中的所有交换需满足以下条件 $P$ ：

对于数组中的任意需要执行交换的两个元素(下标分别为$i$, $j$)，都满足 $nums[i] \mathbin{\&} nums[j] = k$, $k$ 是一个固定数值,

首先，我们来讨论是否存在这样一个值，使得数组中的任意一个数和它的按位与都是一个固定值：

1. $k = 0$, 任何一个数与其相与的结果都是0，所以0是符合整个条件的；

2. $k \neq 0$, 那么 $k$ 的值能是多少？我们发现，对于 $x$ 个数，将其全部执行位与操作得到的值，就是我们想找的 $k$ 的值，因为这个数合并了所有的位与情况；

那么，下一个要克服的难点就是，如何找到这个最大的 $k$ 值。

我们还发现，这个 $k$ 值一定位于 $[0 , n - 1]$ 这个范围, 参考如下公式1

$$a \mathbin{\&} b \leq min(a, b)$$

于是，我们可以换个空间置换思路，那就是假设存在目标值 $k$，以 $k$ 所在的位置为临时空间，将任意其他位置的两个数可以通过 $k$进行互换，$k$的位置不变。

证明

假设要交换的序列为 $num[i], ... , k, ... , num[j]$, 我们知道 $num [i] \mathbin{\&} k = k$ , $num [j] \mathbin{\&} k = k$ , 模拟交换过程如下：

1. 交换$num[i], k$ , 得到 $k, ... , num[i], ... , num[j]$;
2. 交换$k, num[j]$ , 得到 $num[j], ... , num[i], ... , k$;
3. 交换$k, num[i]$, 得到 $num[j], ... , k, ... , num[i]$;

最终我们将$i$, $j$ 两个位置的元素进行了互换。

综上所述，$k$ 值是一定存在的。

那么，问题就变成了如何求 $k$ 的最大值？

如何求解最大的k

我们的目标序列是 $0,1,2,3,...,n-1$，求出最大的符合题意的 $k$ 值，可以分为以下两个步骤：

1. 对于原序列，因为要满足条件 $P$, 针对于所有的 $num[i] \neq i$，必须要参与按位与的累计计算；

2. 对于所有不需要交换的元素，参与到按位与的累积计算中来，看还有没有更大符合题意的值；

在根据步骤1求出上述 $k$ 值后，我们发现根据上文公式1的结论，没有比 $k$ 更大的元素了，所以最终算法只需要执行步骤1

最终代码实现

#include <vector>
using namespace std;
class Solution {
public:
    int sortPermutation(vector<int>& nums) {
        // 步骤1
        int n = nums.size();
        int ans = INT32_MAX;
        bool flag = true; // 记录数组是否有序
        for (int i = 0; i < n; i++) {
            if (nums[i] != i) {
                ans &= nums[i];
                flag = false;
            }
        }

        // 步骤2，不影响结果，可以省略
        for (int i = 0; i < n; i++) {
            if (nums[i] == i) {
                if ((ans & nums[i]) > ans) { // 寻找大最大的值才更新
                    ans = ans & nums[i];
                }
            }
        }

        return flag ? 0 : ans;
    }
};