跳转至

2459. 通过移动项目到空白区域来排序数组 🔒

题目描述

给定一个大小为 n 的整数数组 nums，其中包含从 0 到 n - 1 (包含边界) 的 每个 元素。从 1 到 n - 1 的每一个元素都代表一项目，元素 0 代表一个空白区域。

在一个操作中，您可以将 任何 项目移动到空白区域。如果所有项目的编号都是 升序 的，并且空格在数组的开头或结尾，则认为 nums 已排序。

例如，如果 n = 4，则 nums 按以下条件排序:

  • nums = [0,1,2,3] 或
  • nums = [1,2,3,0]

...否则被认为是无序的。

返回排序 nums 所需的最小操作数。

 

示例 1:

输入: nums = [4,2,0,3,1]
输出: 3
解释:
- 将项目 2 移动到空白区域。现在，nums =[4,0,2,3,1]。
- 将项目 1 移动到空白区域。现在，nums =[4,1,2,3,0]。
- 将项目 4 移动到空白区域。现在，nums =[0,1,2,3,4]。
可以证明，3 是所需的最小操作数。

示例 2:

输入: nums = [1,2,3,4,0]
输出: 0
解释: nums 已经排序了，所以返回 0。

示例 3:

输入: nums = [1,0,2,4,3]
输出: 2
解释:
- 将项目 2 移动到空白区域。现在，nums =[1,2,0,4,3]。
- 将项目 3 移动到空白区域。现在，nums =[1,2,3,4,0]。
可以证明，2 是所需的最小操作数。

 

提示:

  • n == nums.length
  • 2 <= n <= 105
  • 0 <= nums[i] < n
  • nums 的所有值都是 唯一 的。

解法

方法一：置换环

一个长度为 $m$ 的置换环，如果 $0$ 在环中，那么交换次数为 $m-1$，否则交换次数为 $m+1$。

我们找到所有置换环，先按照交换次数为 $m+1$ 计算总的次数，然后判断 $0$ 是否错位，若是，说明 $0$ 在置换环中，那么总的次数减 $2$。

这里 $0$ 可以在 $0$ 位置，也可以在 $n-1$ 位置，我们取这两种情况的最小值。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def sortArray(self, nums: List[int]) -> int:
        def f(nums, k):
            vis = [False] * n
            cnt = 0
            for i, v in enumerate(nums):
                if i == v or vis[i]:
                    continue
                cnt += 1
                j = i
                while not vis[j]:
                    vis[j] = True
                    cnt += 1
                    j = nums[j]
            return cnt - 2 * (nums[k] != k)

        n = len(nums)
        a = f(nums, 0)
        b = f([(v - 1 + n) % n for v in nums], n - 1)
        return min(a, b)

 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
33
class Solution {
    public int sortArray(int[] nums) {
        int n = nums.length;
        int[] arr = new int[n];
        for (int i = 0; i < n; ++i) {
            arr[i] = (nums[i] - 1 + n) % n;
        }
        int a = f(nums, 0);
        int b = f(arr, n - 1);
        return Math.min(a, b);
    }

    private int f(int[] nums, int k) {
        boolean[] vis = new boolean[nums.length];
        int cnt = 0;
        for (int i = 0; i < nums.length; ++i) {
            if (i == nums[i] || vis[i]) {
                continue;
            }
            ++cnt;
            int j = nums[i];
            while (!vis[j]) {
                vis[j] = true;
                ++cnt;
                j = nums[j];
            }
        }
        if (nums[k] != k) {
            cnt -= 2;
        }
        return cnt;
    }
}

 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
class Solution {
public:
    int sortArray(vector<int>& nums) {
        int n = nums.size();
        auto f = [&](vector<int>& nums, int k) {
            vector<bool> vis(n);
            int cnt = 0;
            for (int i = 0; i < n; ++i) {
                if (i == nums[i] || vis[i]) continue;
                int j = i;
                ++cnt;
                while (!vis[j]) {
                    vis[j] = true;
                    ++cnt;
                    j = nums[j];
                }
            }
            if (nums[k] != k) cnt -= 2;
            return cnt;
        };

        int a = f(nums, 0);
        vector<int> arr = nums;
        for (int& v : arr) v = (v - 1 + n) % n;
        int b = f(arr, n - 1);
        return min(a, b);
    }
};

 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
func sortArray(nums []int) int {
    n := len(nums)
    f := func(nums []int, k int) int {
        vis := make([]bool, n)
        cnt := 0
        for i, v := range nums {
            if i == v || vis[i] {
                continue
            }
            cnt++
            j := i
            for !vis[j] {
                vis[j] = true
                cnt++
                j = nums[j]
            }
        }
        if nums[k] != k {
            cnt -= 2
        }
        return cnt
    }
    a := f(nums, 0)
    arr := make([]int, n)
    for i, v := range nums {
        arr[i] = (v - 1 + n) % n
    }
    b := f(arr, n-1)
    return min(a, b)
}

评论