3644. 排序排列
来源第 462 场周赛 Q2难度中等分数1775
题目描述
给你一个长度为 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 <= 1050 <= nums[i] <= n - 1nums是从0到n - 1的一个排列。
解法
方法一:位运算
思考
最直接的做法是从大到小尝试 \(k\),再判断错位元素能否只通过「按位与等于 \(k\)」的交换回到原位。 \(n \le 10^5\),任意两个值都可能满足交换条件,显式建图已经是平方级别,枚举无法通过。
必须移动的是那些不在自身下标上的值。每个这样的值至少参与一次交换,因此 \(k\) 中每一个为 \(1\) 的二进制位,在该值里也必须为 \(1\)。可行的 \(k\) 于是不能超过全体错位值的按位与。
将这个按位与仍然记作 \(k\)。数 \(k\) 属于排列 \([0,n)\),它与任意错位值的按位与都恰好等于 \(k\),故可以作为中转,把错位元素排成任意顺序。若排列已经有序,则不需要交换,答案为 \(0\)。
按位与的单位元是全 \(1\),所以 \(\textit{ans}\) 从 \(-1\) 开始,扫描时只并入满足 \(\textit{nums}[i] \ne i\) 的值。数组有序时 \(\textit{ans}\) 保持 \(-1\),最后与 \(0\) 取较大者即可。
我们用 \(\textit{ans}\) 维护所有不在原位的元素的按位与,初始值为 \(-1\)。
遍历下标 \(i\)。若 \(\textit{nums}[i] \ne i\),则把 \(\textit{nums}[i]\) 按位与进 \(\textit{ans}\)。
扫描结束后,数组有序时 \(\textit{ans}\) 仍为 \(-1\),应当返回 \(0\);否则 \(\textit{ans}\) 就是最大可行的 \(k\)。因此返回 \(\max(\textit{ans}, 0)\)。
时间复杂度 \(O(n)\),空间复杂度 \(O(1)\)。其中 \(n\) 为数组 \(\textit{nums}\) 的长度。
1 2 3 4 5 6 7 | |
1 2 3 4 5 6 7 8 9 10 11 | |
1 2 3 4 5 6 7 8 9 10 11 12 | |
1 2 3 4 5 6 7 8 9 | |
1 2 3 4 5 6 7 8 9 | |
1 2 3 4 5 6 7 8 9 10 11 | |
1 2 3 4 5 6 7 8 9 10 11 | |