跳转至

3644. 排序排列

题目描述

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

解法

方法一

思考

允许交换满足 \(i\land j=k\) 的下标（或值）以使排列归位。不在原位的值必须能通过与 \(k\) 的按位与相互到达。

一次交换不改变「与 \(k\) 的公共 \(1\) 位」。所有错位元素的按位与给出最大可行 \(k\)：更大的 \(k\) 会丢掉某个错位值已有的 \(0\) 位，从而无法交换。

遍历错位对 \(\textit{ans}\) 做与运算，全已有序则 \(k\) 可取 \(0\)。\(\textit{ans}\) 初值 \(-1\) 使与运算从全 \(1\) 开始。

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);
}

评论