1649-通过指令创建有序数组

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:27 2023-09-13 16:06:27 Updated    

给你一个整数数组 instructions ，你需要根据 instructions 中的元素创建一个有序数组。一开始你有一个空的数组 nums
，你需要 从左到右 遍历 instructions 中的元素，将它们依次插入 nums 数组中。每一次插入操作的 代价 是以下两者的
较小值 ：

  • nums 中 严格小于 instructions[i] 的数字数目。
  • nums 中 严格大于 instructions[i] 的数字数目。

比方说，如果要将 3 插入到 nums = [1,2,3,5] ，那么插入操作的 代价 为 min(2, 1) (元素 1 和
2 小于 3 ，元素 5 大于 3 ），插入后 nums 变成 [1,2,3,3,5] 。

请你返回将 instructions 中所有元素依次插入 nums 后的 总最小代价 。由于答案会很大，请将它对 109 + 7
取余 后返回。

示例 1：

**输入：** instructions = [1,5,6,2]
**输出：** 1
**解释：** 一开始 nums = [] 。
插入 1 ，代价为 min(0, 0) = 0 ，现在 nums = [1] 。
插入 5 ，代价为 min(1, 0) = 0 ，现在 nums = [1,5] 。
插入 6 ，代价为 min(2, 0) = 0 ，现在 nums = [1,5,6] 。
插入 2 ，代价为 min(1, 2) = 1 ，现在 nums = [1,2,5,6] 。
总代价为 0 + 0 + 0 + 1 = 1 。

示例 2:

**输入：** instructions = [1,2,3,6,5,4]
**输出：** 3
**解释：** 一开始 nums = [] 。
插入 1 ，代价为 min(0, 0) = 0 ，现在 nums = [1] 。
插入 2 ，代价为 min(1, 0) = 0 ，现在 nums = [1,2] 。
插入 3 ，代价为 min(2, 0) = 0 ，现在 nums = [1,2,3] 。
插入 6 ，代价为 min(3, 0) = 0 ，现在 nums = [1,2,3,6] 。
插入 5 ，代价为 min(3, 1) = 1 ，现在 nums = [1,2,3,5,6] 。
插入 4 ，代价为 min(3, 2) = 2 ，现在 nums = [1,2,3,4,5,6] 。
总代价为 0 + 0 + 0 + 0 + 1 + 2 = 3 。

示例 3：

**输入：** instructions = [1,3,3,3,2,4,2,1,2]
**输出：** 4
**解释：** 一开始 nums = [] 。
插入 1 ，代价为 min(0, 0) = 0 ，现在 nums = [1] 。
插入 3 ，代价为 min(1, 0) = 0 ，现在 nums = [1,3] 。
插入 3 ，代价为 min(1, 0) = 0 ，现在 nums = [1,3,3] 。
插入 3 ，代价为 min(1, 0) = 0 ，现在 nums = [1,3,3,3] 。
插入 2 ，代价为 min(1, 3) = 1 ，现在 nums = [1,2,3,3,3] 。
插入 4 ，代价为 min(5, 0) = 0 ，现在 nums = [1,2,3,3,3,4] 。
​​​​​插入 2 ，代价为 min(1, 4) = 1 ，现在 nums = [1,2,2,3,3,3,4] 。
插入 1 ，代价为 min(0, 6) = 0 ，现在 nums = [1,1,2,2,3,3,3,4] 。
插入 2 ，代价为 min(2, 4) = 2 ，现在 nums = [1,1,2,2,2,3,3,3,4] 。
总代价为 0 + 0 + 0 + 0 + 1 + 0 + 1 + 0 + 2 = 4 。

提示：

  • 1 <= instructions.length <= 105
  • 1 <= instructions[i] <= 105

前言

分析题目要求，需要实现三个操作：

  • 向数据结构中添加一个元素 x；

  • 给定一个元素 x，查询数据结构中在 [1, x-1] 范围内的元素个数；

  • 给定一个元素 x，查询数据结构在 [x+1, \textit{UB}] 范围内的元素个数，其中 UB 表示所有涉及到操作的元素的最大值，在本题中这个值不会超过 10^5。

因此可以用任一常见数据结构完成本题，可以参考下面两个链接：

方法一：线段树

[sol1-C++]
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
class SegTree {
private:
    int n;
    vector<int> segnode;

private:
    void update_(int id, int l, int r, int x) {
        if (l > x || r < x) {
            return;
        }
        ++segnode[id];
        if (l == r) {
            return;
        }
        int mid = (l + r) >> 1;
        update_(id * 2 + 1, l, mid, x);
        update_(id * 2 + 2, mid + 1, r, x);
    }

    int query_(int id, int l, int r, int ql, int qr) const {
        if (l > qr || r < ql) {
            return 0;
        }
        if (ql <= l && r <= qr) {
            return segnode[id];
        }
        int mid = (l + r) >> 1;
        return query_(id * 2 + 1, l, mid, ql, qr) + query_(id * 2 + 2, mid + 1, r, ql, qr);
    }

public:
    SegTree(int _n): n(_n), segnode(_n * 4) {}

    void update(int x) {
        update_(0, 1, n, x);
    }

    int query(int left, int right) const {
        return query_(0, 1, n, left, right);
    }
};

class Solution {
private:
    static constexpr int mod = 1000000007;

public:
    int createSortedArray(vector<int>& instructions) {
        int ub = *max_element(instructions.begin(), instructions.end());
        SegTree tree(ub);
        long long ans = 0;
        for (int i = 0; i < instructions.size(); ++i) {
            int x = instructions[i];
            int smaller = tree.query(1, x - 1);
            int larger = tree.query(x + 1, ub);
            ans += min(smaller, larger);
            tree.update(x);
        }
        return ans % mod;
    }
};

方法二：树状数组

[sol2-C++]
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
class BIT {
private:
    int n;
    vector<int> tree;

public:
    BIT(int _n): n(_n), tree(_n + 1) {}

    static constexpr int lowbit(int x) {
        return x & (-x);
    }
    
    void update(int x) {
        while (x <= n) {
            ++tree[x];
            x += lowbit(x);
        }
    }

    int query(int x) const {
        int ans = 0;
        while (x) {
            ans += tree[x];
            x -= lowbit(x);
        }
        return ans;
    }
};

class Solution {
private:
    static constexpr int mod = 1000000007;

public:
    int createSortedArray(vector<int>& instructions) {
        int ub = *max_element(instructions.begin(), instructions.end());
        BIT bit(ub);
        long long ans = 0;
        for (int i = 0; i < instructions.size(); ++i) {
            int x = instructions[i];
            int smaller = bit.query(x - 1);
            int larger = i - bit.query(x);
            ans += min(smaller, larger);
            bit.update(x);
        }
        return ans % mod;
    }
};

方法三：平衡树

[sol3-C++]
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
class BalancedTree {
private:
    struct BalancedNode {
        int val;
        int seed;
        int count;
        int size;
        BalancedNode* left;
        BalancedNode* right;

        BalancedNode(int _val, int _seed): val(_val), seed(_seed), count(1), size(1), left(nullptr), right(nullptr) {}

        BalancedNode* left_rotate() {
            int prev_size = size;
            int curr_size = (left ? left->size : 0) + (right->left ? right->left->size : 0) + count;
            BalancedNode* root = right;
            right = root->left;
            root->left = this;
            root->size = prev_size;
            size = curr_size;
            return root;
        }

        BalancedNode* right_rotate() {
            int prev_size = size;
            int curr_size = (right ? right->size : 0) + (left->right ? left->right->size : 0) + count;
            BalancedNode* root = left;
            left = root->right;
            root->right = this;
            root->size = prev_size;
            size = curr_size;
            return root;
        }
    };

private:
    BalancedNode* root;
    int size;
    mt19937 gen;
    uniform_int_distribution<int> dis;

private:
    BalancedNode* insert_(BalancedNode* node, int x) {
        if (!node) {
            return new BalancedNode(x, dis(gen));
        }
        ++node->size;
        if (x < node->val) {
            node->left = insert_(node->left, x);
            if (node->left->seed > node->seed) {
                node = node->right_rotate();
            }
        }
        else if (x > node->val) {
            node->right = insert_(node->right, x);
            if (node->right->seed > node->seed) {
                node = node->left_rotate();
            }
        }
        else {
            ++node->count;
        }
        return node;
    }

public:
    BalancedTree(): root(nullptr), size(0), gen(random_device{}()), dis(INT_MIN, INT_MAX) {}

    int get_size() const {
        return size;
    }

    void insert(int x) {
        ++size;
        root = insert_(root, x);
    }

    int lower_bound(int x) const {
        BalancedNode* node = root;
        int ans = INT_MAX;
        while (node) {
            if (x == node->val) {
                return x;
            }
            if (x < node->val) {
                ans = node->val;
                node = node->left;
            }
            else {
                node = node->right;
            }
        }
        return ans;
    }

    int upper_bound(int x) const {
        BalancedNode* node = root;
        int ans = INT_MAX;
        while (node) {
            if (x < node->val) {
                ans = node->val;
                node = node->left;
            }
            else {
                node = node->right;
            }
        }
        return ans;
    }

    pair<int, int> rank(int x) const {
        BalancedNode* node = root;
        int ans = 0;
        while (node) {
            if (x < node->val) {
                node = node->left;
            }
            else {
                ans += (node->left ? node->left->size : 0) + node->count;
                if (x == node->val) {
                    return {ans - node->count + 1, ans};
                }
                node = node->right;
            }
        }
        return {INT_MIN, INT_MAX};
    }
};

class Solution {
private:
    static constexpr int mod = 1000000007;

public:
    int createSortedArray(vector<int>& instructions) {
        BalancedTree treap;
        long long ans = 0;
        for (int i = 0; i < instructions.size(); ++i) {
            int x = instructions[i];
            int lb = treap.lower_bound(x);
            int smaller = (lb == INT_MAX ? i : treap.rank(lb).first - 1);
            int rb = treap.upper_bound(x);
            int larger = (rb == INT_MAX ? 0 : i - treap.rank(rb).first + 1);
            ans += min(smaller, larger);
            treap.insert(x);
        }
        return ans % mod;
    }
};

方法四：Python 天下第一

这个方法的时间复杂度未知，因为我也不太清楚 Python 列表的底层实现是啥，不过确实挺快，但在竞赛中还是不推荐写这种方法。

[sol4-Python3]
1
2
3
4
5
6
7
8
9
10
class Solution:
    def createSortedArray(self, instructions: List[int]) -> int:
        ans = 0
        ordered = list()
        for x in instructions:
            smaller = bisect.bisect_left(ordered, x)
            larger = len(ordered) - bisect.bisect_right(ordered, x)
            ans += min(smaller, larger)
            ordered[smaller:smaller] = [x]
        return ans % (10**9 + 7)
 Comments
On this page
1649-通过指令创建有序数组