列表

详情

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

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

比方说，如果要将 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 。

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: int createSortedArray(vector<int>& instructions) { } };

php 解法, 执行用时: 1024 ms, 内存消耗: 31.3 MB, 提交时间: 2023-10-08 23:29:30 

class BIT
{
    private $n;
    private $tree;
    function __construct($n)
    {
        $this->n = $n;
        $this->tree = array_fill(0, $n + 1, 0);
    }

    function lowbit($x)
    {
        return $x & (-$x);
    }

    function update($x)
    {
        while ($x <= $this->n) {
            ++$this->tree[$x];
            $x += $this->lowbit($x);
        }
    }

    function query($x)
    {
        $ans = 0;
        while ($x) {
            $ans += $this->tree[$x];
            $x -= $this->lowbit($x);
        }
        return $ans;
    }
}

class Solution
{
    /**
     * @param int[] $instructions
     * @return Integer
     */
    function createSortedArray($instructions)
    {
        $bit = new BIT(max($instructions));
        $ans = 0;
        for ($i = 0; $i < count($instructions); ++$i) {
            $x = $instructions[$i];
            $smaller = $bit->query($x - 1);
            $larger = $i - $bit->query($x);
            $ans += min($smaller, $larger);
            $bit->update($x);
        }
        return $ans % 1000000007;
    }
}

java 解法, 执行用时: 96 ms, 内存消耗: 63.5 MB, 提交时间: 2023-10-08 23:28:57 

class Solution {
    public int createSortedArray(int[] instructions) {
		int mod = (int)1e9 + 7;
		long ans = 0;
		Set<Integer> set = new HashSet<>();
		for(int i = 0; i < instructions.length; ++i) {
			set.add(instructions[i]);
		}
		int[] nums = new int[set.size()];
		int index = 0;
		for(int num: set) {
			nums[index++] = num;
		}
		Arrays.sort(nums);
		Map<Integer, Integer> map = new HashMap<>();
		for(int i = 0; i < nums.length; ++i) {
			map.put(nums[i], i + 1);
		}
        
		BIT bit = new BIT(nums.length);

		for(int i = 0; i < instructions.length; ++i) {
            
			int t = map.get(instructions[i]);
			int l = bit.getSum(t - 1);
			int r = bit.getSum(t);
            // System.out.println(l);
            // System.out.println(r);
			ans += Math.min(l, i - r);
			ans %= mod;
			bit.update(t, 1);
		}
		return (int) ans;
	}
}

class BIT {
	int n;
	int[] tree;
	public BIT(int n) {
		this.n = n;
		tree = new int[n + 1];
	}

	public void update(int i, int val) {
		while(i <= n) {
			tree[i] += val;
			i += lowbit(i);
		}
	}

	public int getSum(int i) {
		int res = 0;
		while(i > 0) {
			res += tree[i];
			i -= lowbit(i);
		}
		return res;
	}

	public int lowbit(int x) {
		return x & (-x);
	}
}

golang 解法, 执行用时: 184 ms, 内存消耗: 9.2 MB, 提交时间: 2023-10-08 23:28:20 

func createSortedArray(instructions []int) (cnt int) {
	mod := 1000000007
	tree := make([]int, 100001)
	var sum func(i int) int
	sum = func(i int) (x int) {
		for j := i; j > 0; j -= (j & -j) {
			x += tree[j]
		}
		return
	}
	for _, i := range instructions {
		for j := i; j < len(tree); j += (j & -j) {
			tree[j]++
		}
		cnt = (cnt + min(sum(i-1), sum(100000)-sum(i))) % mod
	}
	return
}

func min(a, b int) int { if a < b { return a }; return b }

golang 解法, 执行用时: 200 ms, 内存消耗: 14.1 MB, 提交时间: 2023-10-08 23:27:49 

var (
    nums, tree      []int
)

func lowbit(x int) int {
    return x&(-x)
}

func add(i, v int) {
    for i <= len(nums) {
        tree[i] += v
        i += lowbit(i)
    }
}
func sum(i int) int {
    res := 0
    for i > 0 {
        res += tree[i]
        i -= lowbit(i)
    }
    return res
}

func sumFromTo(i, j int) int {
    return sum(j)-sum(i-1)
}


func createSortedArray(instructions []int) int {
    MOD := 1000000007
    min := func(a, b int) int {
        if a < b {
            return a
        }
        return b
    }

    nums = make([]int, 100000)
    tree = make([]int, len(nums)*2)

    res := 0

    for i := range instructions {
        lessCount := sum(instructions[i]-1)
        largerCount := i - sum(instructions[i])
        res += min(lessCount, largerCount)
        res %= MOD
        add(instructions[i], 1)
    }

    return res
}

python3 解法, 执行用时: 2452 ms, 内存消耗: 27.7 MB, 提交时间: 2023-10-08 23:27:17 

class Solution:
    def createSortedArray(self, instructions: List[int]) -> int:
        def add(x: int) -> None:
            # 将x插入到树状数组中
            while x < n:
                nums[x] += 1
                x += (x & -x)

        def getSum(x: int) -> int:
            # 求出小于等于x的元素个数
            res = 0
            while x > 0:
                res += nums[x]
                x -= (x & -x)
            return res

        # 创建树状数组
        n = max(instructions) + 1
        nums = [0 for _ in range(n)]
        # res为总代价
        res = 0
        # cnt为当前存在元素
        cnt = 0
        for i in instructions:
            # getSum(i-1)求比自己小的元素个数
            # cnt - getSum(i)求比自己大的元素个数
            res = (res + min(getSum(i - 1), cnt - getSum(i))) % (10 ** 9 + 7)
            add(i)
            cnt += 1
        return res

python3 解法, 执行用时: 4228 ms, 内存消耗: 28.2 MB, 提交时间: 2023-10-08 23:26:53 

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)

cpp 解法, 执行用时: 744 ms, 内存消耗: 224.3 MB, 提交时间: 2023-10-08 23:26:36 

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

cpp 解法, 执行用时: 232 ms, 内存消耗: 114.2 MB, 提交时间: 2023-10-08 23:26:20 

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

cpp 解法, 执行用时: 512 ms, 内存消耗: 121.3 MB, 提交时间: 2023-10-08 23:26:09 

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

上一题

© 2024 leetcode.cn