Leetcode 1409:查询带键的排列(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1409:查询带键的排列(超详细的解法!!!)

in leetcode with 0 comment

给你一个待查数组 queries ,数组中的元素为 1m 之间的正整数。 请你根据以下规则处理所有待查项 queries[i](从 i=0i=queries.length-1):

请你以数组形式返回待查数组 queries 的查询结果。

示例 1:

输入:queries = [3,1,2,1], m = 5
输出:[2,1,2,1] 
解释:待查数组 queries 处理如下:
对于 i=0: queries[i]=3, P=[1,2,3,4,5], 3 在 P 中的位置是 2,接着我们把 3 移动到 P 的起始位置,得到 P=[3,1,2,4,5] 。
对于 i=1: queries[i]=1, P=[3,1,2,4,5], 1 在 P 中的位置是 1,接着我们把 1 移动到 P 的起始位置,得到 P=[1,3,2,4,5] 。 
对于 i=2: queries[i]=2, P=[1,3,2,4,5], 2 在 P 中的位置是 2,接着我们把 2 移动到 P 的起始位置,得到 P=[2,1,3,4,5] 。
对于 i=3: queries[i]=1, P=[2,1,3,4,5], 1 在 P 中的位置是 1,接着我们把 1 移动到 P 的起始位置,得到 P=[1,2,3,4,5] 。 
因此,返回的结果数组为 [2,1,2,1] 。  

示例 2:

输入:queries = [4,1,2,2], m = 4
输出:[3,1,2,0]

示例 3:

输入:queries = [7,5,5,8,3], m = 8
输出:[6,5,0,7,5]

提示:

解题思路

首先不难想到暴力解法,也就是模拟题目中的操作。

class Solution:
    def processQueries(self, queries: List[int], m: int) -> List[int]:
        res = []
        P = list(range(1, m + 1))
        for q in queries:
            for i, v in enumerate(P):
                if v == q:
                    res.append(i)
                    break
            P = [v] + P[:i] + P[i+1:]
        return res

这个问题也可以通过平衡树来处理,在P元素和位置之间建立映射(树的key存位置),对于每次查找到的元素,首先从树中删除,然后再插入树中(此时的位置为0)。但是这样做的话,每次查找元素的操作,还是需要遍历整棵树。

有没有更好的解法呢?这个问题可以转化为区间查询问题,可以将建立一个大小为m+len(q)的数组,然后将后m位的值标记为1,对于例1就是:

0 0 0 0 0 | 1 1 1 1
                ↑

此时查询3的位置,就是查询len(q)+3-1前有多少个1。当查询结束后,需要将len(q)+3-1置为0,然后将len(q)-1置为1(此步就是将3放到了数组的首位)。

0 0 0 0 1 | 1 1 0 1
            ↑

接着查询1的位置按上述方法同理即可。最后还有一个问题就是数据移动后的位置变化,这需要一个新的数组去记录位置信息。关于区间查询和区间维护可以通过树状数组处理。

class Solution:
    def processQueries(self, queries: List[int], m: int) -> List[int]:
        n = len(queries)
        tree, pos = [0] * (m + n + 1), [0] * (m + 1)
        res = []
        
        def update(i, v):
            while i < len(tree):
                tree[i] += v
                i += i & -i
    
        def prefixSum(i):
            res = 0 
            while i:
                res += tree[i]
                i -= i & -i
            return res

        for i in range(1, m + 1):
            update(i + n, 1)
            pos[i] = n + i

        for i in queries:
            res.append(prefixSum(pos[i] - 1))
            update(pos[i], -1)
            update(n, 1)
            pos[i] = n
            n -= 1
        return res

reference:

https://leetcode.com/problems/queries-on-a-permutation-with-key/discuss/575071/PythonC%2B%2B-NlogN-Short-Fenwick-Tree-With-Detailed-Explanations

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses