leet3644.Maximum K to Sort a Permutation

题目描述

You are given an integer array nums of length n, where nums is a permutation of the numbers in the range [0..n - 1].

You may swap elements at indices i and j only if nums[i] AND nums[j] == k, where AND denotes the bitwise AND operation and k is a non-negative integer.

Return the maximum value of k such that the array can be sorted in non-decreasing order using any number of such swaps. If nums is already sorted, return 0.

Example 1:

Input: nums = [0,3,2,1]

Output: 1

Explanation:

Choose k = 1. Swapping nums[1] = 3 and nums[3] = 1 is allowed since nums[1] AND nums[3] == 1, resulting in a sorted permutation: [0, 1, 2, 3].

Example 2:

Input: nums = [0,1,3,2]

Output: 2

Explanation:

Choose k = 2. Swapping nums[2] = 3 and nums[3] = 2 is allowed since nums[2] AND nums[3] == 2, resulting in a sorted permutation: [0, 1, 2, 3].

Example 3:

Input: nums = [3,2,1,0]

Output: 0

Explanation:

Only k = 0 allows sorting since no greater k allows the required swaps where nums[i] AND nums[j] == k.

Constraints:

• 1 <= n == nums.length <= 10^5
• 0 <= nums[i] <= n - 1
• nums is a permutation of integers from 0 to n - 1.

---

思路

先说结论，这题答案其实见就是把所有 $nums[i]\ne i$ 的元素按位与起来。先承认这个结论，写起来很简单。

int sortPermutation(vector<int>& nums) {
    int k = -1;
    for (int i = 0; i < nums.size(); ++i) {
        if (nums[i] == i) continue;
        if (k == -1) {
            k = nums[i];
            continue;
        }
        k &= nums[i];
    }
    return k == -1 ? 0 : k;
}

那为什么上面的结论成立呢？首先理解下题意，题干上说 nums 是 0到 n - 1的一个排列。要想把它变得有序，那么最终nums肯定就是 0到 n - 1 依次递增，即满足 $nums[i]=i$. 现在考虑那些不满足这个条件的元素，即不在其位的元素，错位元素，交换仅需在它们之间发生。但仔细看一下交换的条件，nums[i] & nums[j] == k. 先把两个数都表示为二进制格式，按位与的结果其实就是保留那些二进制位，在这些二进制位上，它们的取值都是 1.例如，

  0b0110
& 0b1010
---------
  0b0010

可以看到，按位与的结果只在低二位上为 1，因为原二数在这个位上都是 1. 这告诉我们什么呢？如果把 k 表示成二进制，那它仅在原二数为 1 的那些二进制位上为 1，其他二进制位为 0. 也就是说，

• nums[i] & k == k
• nums[j] & k == k

这说明，要交换的元素必须都满足 nums[i] & k == k，这意味着 k 中的每一个 1 必须出现在所有要交换的元素当中。因为与运算越与结果越小（因为与不可能增加二进制 1 的个数，只会减少），所以 k 的最大值就是那些不在其位的元素按位与的结果。同理¹，

$$k\le n-1.$$

这说明 k 就在 nums 中。而任意两个错位元素，都可以通过 k 中转来交换。下面分类讨论。

如果 k 本身不是错位元素，现有两个错位元素 a，b。初始时，他们的相对顺序是 k, a, b, 下面演示如何交换，

1. 交换 k，a 得 a，k，b。因为 a & k == k.
2. 交换 k，b 得a，b，k。
3. 交换a，k 得 k，b，a。至此，a、b 完成交换，且 k 回到原位。

如果 k 本身就是错位元素，设 k 原本应该在第 i 位上，显然当前的 nums[i] 也是一个错位元素，因为它占了 k 的位置。直接交换 nums[i] 和 k，交换后，k 就不是错位元素了，直接套用上面的结论即可。

综上所述，k（所有错位元素相与的结果）就是我们要找的答案。

---

see also 神奇的位运算

Footnotes

1. 因为越与越小，而 k 是 nums 中所有错位元素相与的结果，nums 中最大元素也就是 n - 1. ↩