跳转至

3991. 使用前缀反转对数组进行排序 🔒

题目描述

给你一个长度为 n 的整数数组 nums，其中 nums 是区间 [0, n - 1] 内整数的一个 排列。

另给你一个整数数组 pre，其中每个 pre[i] 都是一个合法的 前缀 长度。

一次操作中，你可以从 pre 中选择任意一个长度 x，并将 nums 的前 x 个元素翻转。

例如，对数组 [4, 1, 2, 3] 执行一次长度为 3 的前缀翻转后，结果为 [2, 1, 4, 3]。

返回将 nums 按升序排序所需的最少操作次数。如果无法完成排序，则返回 -1。

 

示例 1：

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

输出： 2

解释：

  • 先翻转前 pre[1] = 3 个元素，得到 nums = [1, 0, 2]。
  • 然后翻转前 pre[0] = 2 个元素，得到 nums = [0, 1, 2]。
  • 因此，将数组排序所需的最少前缀翻转次数为 2。

示例 2：

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

输出： -1

解释：

无法仅使用给定的前缀长度对数组进行排序，因此答案为 -1。

示例 3：

输入： nums = [0,1], pre = [2]

输出： 0

解释：

由于 nums 已经按升序排列，因此无需进行任何前缀翻转操作，答案为 0。

 

约束条件：

  • 1 <= n == nums.length <= 8
  • 0 <= nums[i] <= n - 1
  • 1 <= pre.length <= n
  • 1 <= pre[i] <= n
  • nums 是由 0 到 n - 1 所有整数组成的一个排列。
  • pre 中的所有整数 互不相同。

解法

方法一：BFS

由于 \(n \le 8\)，排列的状态总数不超过 \(8! = 40320\)，可以用广度优先搜索求最少操作次数。

将当前数组视为一个状态，目标状态为 \([0, 1, \ldots, n - 1]\)。若初始状态已是目标状态，直接返回 \(0\)。否则从初始状态出发进行 BFS：每次取出一个状态，枚举 \(\textit{pre}\) 中的每个前缀长度 \(x\)，翻转该状态的前 \(x\) 个元素得到新状态。若新状态等于目标状态，返回当前步数；否则若尚未访问过，则加入队列继续搜索。若搜索结束仍未到达目标状态，返回 \(-1\)。

为方便判重，可将排列编码为以 \(8\) 为进制的整数（每个元素均落在 \([0, 7]\) 内）。

时间复杂度 \(O(n! \cdot m \cdot n)\)，空间复杂度 \(O(n! \cdot n)\)。其中 \(n\) 是数组长度，\(m\) 是 \(\textit{pre}\) 的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def sortArray(self, nums: List[int], pre: List[int]) -> int:
        n = len(nums)
        target = tuple(range(n))
        start = tuple(nums)

        if start == target:
            return 0

        vis = {start}
        q = deque([(start, 0)])

        while q:
            state, dist = q.popleft()
            nd = dist + 1
            for x in pre:
                nxt = state[:x][::-1] + state[x:]
                if nxt == target:
                    return nd
                if nxt not in vis:
                    vis.add(nxt)
                    q.append((nxt, nd))
        return -1

 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
    public int sortArray(int[] nums, int[] pre) {
        int n = nums.length;

        int target = 0;
        for (int i = 0; i < n; i++) {
            target = target * 8 + i;
        }

        int start = 0;
        for (int x : nums) {
            start = start * 8 + x;
        }

        if (start == target) {
            return 0;
        }

        Set<Integer> vis = new HashSet<>();
        vis.add(start);

        Deque<int[]> q = new ArrayDeque<>();
        Deque<Integer> dist = new ArrayDeque<>();
        q.offer(nums.clone());
        dist.offer(0);

        while (!q.isEmpty()) {
            int[] state = q.poll();
            int d = dist.poll();
            int nd = d + 1;

            for (int x : pre) {
                int[] nxt = state.clone();

                int l = 0, r = x - 1;
                while (l < r) {
                    int t = nxt[l];
                    nxt[l] = nxt[r];
                    nxt[r] = t;
                    l++;
                    r--;
                }

                int key = 0;
                for (int v : nxt) {
                    key = key * 8 + v;
                }

                if (key == target) {
                    return nd;
                }

                if (vis.add(key)) {
                    q.offer(nxt);
                    dist.offer(nd);
                }
            }
        }

        return -1;
    }
}

 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public:
    int sortArray(vector<int>& nums, vector<int>& pre) {
        int n = nums.size();

        int target = 0;
        for (int i = 0; i < n; i++) {
            target = target * 8 + i;
        }

        int start = 0;
        for (int x : nums) {
            start = start * 8 + x;
        }

        if (start == target) {
            return 0;
        }

        unordered_set<int> vis;
        vis.insert(start);

        queue<pair<vector<int>, int>> q;
        q.emplace(nums, 0);

        while (!q.empty()) {
            auto [state, dist] = q.front();
            q.pop();

            int nd = dist + 1;

            for (int x : pre) {
                vector<int> nxt = state;
                reverse(nxt.begin(), nxt.begin() + x);

                int key = 0;
                for (int v : nxt) {
                    key = key * 8 + v;
                }

                if (key == target) {
                    return nd;
                }

                if (vis.insert(key).second) {
                    q.emplace(move(nxt), nd);
                }
            }
        }

        return -1;
    }
};

 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
func sortArray(nums []int, pre []int) int {
    n := len(nums)

    target := 0
    for i := 0; i < n; i++ {
        target = target*8 + i
    }

    start := 0
    for _, x := range nums {
        start = start*8 + x
    }

    if start == target {
        return 0
    }

    vis := map[int]bool{start: true}

    type pair struct {
        state []int
        dist  int
    }
    q := []pair{{append([]int(nil), nums...), 0}}

    for len(q) > 0 {
        p := q[0]
        q = q[1:]

        state := p.state
        dist := p.dist
        nd := dist + 1

        for _, x := range pre {
            nxt := append([]int(nil), state...)

            for l, r := 0, x-1; l < r; l, r = l+1, r-1 {
                nxt[l], nxt[r] = nxt[r], nxt[l]
            }

            key := 0
            for _, v := range nxt {
                key = key*8 + v
            }

            if key == target {
                return nd
            }

            if !vis[key] {
                vis[key] = true
                q = append(q, pair{nxt, nd})
            }
        }
    }

    return -1
}

 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
function sortArray(nums: number[], pre: number[]): number {
    const n = nums.length;

    let target = 0;
    for (let i = 0; i < n; i++) {
        target = target * 8 + i;
    }

    let start = 0;
    for (const x of nums) {
        start = start * 8 + x;
    }

    if (start === target) {
        return 0;
    }

    const vis = new Set<number>();
    vis.add(start);

    const q: [number[], number][] = [[nums.slice(), 0]];

    while (q.length) {
        const [state, dist] = q.shift()!;
        const nd = dist + 1;

        for (const x of pre) {
            const nxt = state.slice();

            for (let l = 0, r = x - 1; l < r; l++, r--) {
                [nxt[l], nxt[r]] = [nxt[r], nxt[l]];
            }

            let key = 0;
            for (const v of nxt) {
                key = key * 8 + v;
            }

            if (key === target) {
                return nd;
            }

            if (!vis.has(key)) {
                vis.add(key);
                q.push([nxt, nd]);
            }
        }
    }

    return -1;
}

评论