跳转至

3431. 对数字排序的最小解锁下标 🔒

题目描述

给定一个仅包含 1、2、3 的整数的数组 nums，以及一个相同大小的 二进制 数组 locked。

当满足 nums[i] - nums[i + 1] == 1 且 locked[i] == 0时，则允许交换下标 i 和 i + 1 处的元素；如果可以通过交换相邻元素将 nums 升序排序，我们认为 nums 是 可排序的。

你可以进行若干次操作，每次操作可以将 locked[i] 设置为 0，从而解锁下标 i。

返回使 nums 满足 可排序的 所需 最小 操作次数。如果不可能使 nums 可排序，返回 -1。

 

示例 1：

输入：nums = [1,2,1,2,3,2], locked = [1,0,1,1,0,1]

输出：0

解释：

我们可以按如下交换来排序 nums。

  • 交换下标 1 和 2
  • 交换下标 4 和 5

所以，不需要解锁任何下标。

示例 2：

输入：nums = [1,2,1,1,3,2,2], locked = [1,0,1,1,0,1,0]

输出：2

解释：

如果我们解锁下标 2 和 5，我们可以按如下交换来排序 nums。

  • 交换下标 1 和 2
  • 交换下标 2 和 3
  • 交换下标 4 和 5
  • 交换下标 5 和 6

示例 3：

输入：nums = [1,2,1,2,3,2,1], locked = [0,0,0,0,0,0,0]

输出：-1

解释：

尽管所有下标都是解锁的，可以发现 nums 不可排序。

 

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 3
  • locked.length == nums.length
  • 0 <= locked[i] <= 1

解法

方法一：脑筋急转弯

根据题目描述，要使得 $\textit{nums}$ 变成可排序的数组，需要满足数字 $3$ 的位置在数字 $1$ 的位置之后。如果数字 $3$ 的位置在数字 $1$ 的位置之前，那么无论怎么交换，数字 $3$ 都无法到达数字 $1$ 的位置，因此无法使得 $\textit{nums}$ 变成可排序的数组。

我们分别用 $\textit{first2}$ 和 $\textit{first3}$ 表示数字 $2$ 和 $3$ 第一次出现的位置，用 $\textit{last1}$ 和 $\textit{last2}$ 表示数字 $1$ 和 $2$ 最后一次出现的位置。

那么当下标 $i$ 位于 $[\textit{first2}, \textit{last1})$ 或者 $[\textit{first3}, \textit{last2})]$ 时，对应的 $\textit{locked}[i]$ 必须为 $0$，否则我们需要一次操作。因此，我们只需要遍历数组 $\textit{locked}$，统计不满足条件的下标即可。

时间复杂度 $O(n)$，其中 $n$ 为数组 $\textit{nums}$ 的长度。空间复杂度 $O(1)$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def minUnlockedIndices(self, nums: List[int], locked: List[int]) -> int:
        n = len(nums)
        first2 = first3 = n
        last1 = last2 = -1
        for i, x in enumerate(nums):
            if x == 1:
                last1 = i
            elif x == 2:
                first2 = min(first2, i)
                last2 = i
            else:
                first3 = min(first3, i)
        if first3 < last1:
            return -1
        return sum(
            st and (first2 <= i < last1 or first3 <= i < last2)
            for i, st in enumerate(locked)
        )

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int minUnlockedIndices(int[] nums, int[] locked) {
        int n = nums.length;
        int first2 = n, first3 = n;
        int last1 = -1, last2 = -1;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 1) {
                last1 = i;
            } else if (nums[i] == 2) {
                first2 = Math.min(first2, i);
                last2 = i;
            } else {
                first3 = Math.min(first3, i);
            }
        }
        if (first3 < last1) {
            return -1;
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (locked[i] == 1 && ((first2 <= i && i < last1) || (first3 <= i && i < last2))) {
                ++ans;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int minUnlockedIndices(vector<int>& nums, vector<int>& locked) {
        int n = nums.size();
        int first2 = n, first3 = n;
        int last1 = -1, last2 = -1;

        for (int i = 0; i < n; ++i) {
            if (nums[i] == 1) {
                last1 = i;
            } else if (nums[i] == 2) {
                first2 = min(first2, i);
                last2 = i;
            } else {
                first3 = min(first3, i);
            }
        }

        if (first3 < last1) {
            return -1;
        }

        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (locked[i] == 1 && ((first2 <= i && i < last1) || (first3 <= i && i < last2))) {
                ++ans;
            }
        }

        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func minUnlockedIndices(nums []int, locked []int) (ans int) {
    n := len(nums)
    first2, first3 := n, n
    last1, last2 := -1, -1
    for i, x := range nums {
        if x == 1 {
            last1 = i
        } else if x == 2 {
            if i < first2 {
                first2 = i
            }
            last2 = i
        } else {
            if i < first3 {
                first3 = i
            }
        }
    }
    if first3 < last1 {
        return -1
    }
    for i, st := range locked {
        if st == 1 && ((first2 <= i && i < last1) || (first3 <= i && i < last2)) {
            ans++
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function minUnlockedIndices(nums: number[], locked: number[]): number {
    const n = nums.length;
    let [first2, first3] = [n, n];
    let [last1, last2] = [-1, -1];

    for (let i = 0; i < n; i++) {
        if (nums[i] === 1) {
            last1 = i;
        } else if (nums[i] === 2) {
            first2 = Math.min(first2, i);
            last2 = i;
        } else {
            first3 = Math.min(first3, i);
        }
    }

    if (first3 < last1) {
        return -1;
    }

    let ans = 0;
    for (let i = 0; i < n; i++) {
        if (locked[i] === 1 && ((first2 <= i && i < last1) || (first3 <= i && i < last2))) {
            ans++;
        }
    }

    return ans;
}

评论