跳转至

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 <= 105
  • 0 <= nums[i] <= n - 1
  • nums 是从 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
class Solution:
    def sortPermutation(self, nums: list[int]) -> int:
        ans = -1
        for i, x in enumerate(nums):
            if i != x:
                ans &= x
        return max(ans, 0)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public int sortPermutation(int[] nums) {
        int ans = -1;
        for (int i = 0; i < nums.length; ++i) {
            if (i != nums[i]) {
                ans &= nums[i];
            }
        }
        return Math.max(ans, 0);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int sortPermutation(vector<int>& nums) {
        int ans = -1;
        for (int i = 0; i < nums.size(); ++i) {
            if (i != nums[i]) {
                ans &= nums[i];
            }
        }
        return max(ans, 0);
    }
};
1
2
3
4
5
6
7
8
9
func sortPermutation(nums []int) int {
    ans := -1
    for i, x := range nums {
        if i != x {
            ans &= x
        }
    }
    return max(ans, 0)
}
1
2
3
4
5
6
7
8
9
function sortPermutation(nums: number[]): number {
    let ans = -1;
    for (let i = 0; i < nums.length; ++i) {
        if (i != nums[i]) {
            ans &= nums[i];
        }
    }
    return Math.max(ans, 0);
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
impl Solution {
    pub fn sort_permutation(nums: Vec<i32>) -> i32 {
        let mut ans = -1;
        for (i, &x) in nums.iter().enumerate() {
            if i as i32 != x {
                ans &= x;
            }
        }
        ans.max(0)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
public class Solution {
    public int SortPermutation(int[] nums) {
        int ans = -1;
        for (int i = 0; i < nums.Length; i++) {
            if (i != nums[i]) {
                ans &= nums[i];
            }
        }
        return Math.Max(ans, 0);
    }
}

评论