Medium

题目描述

给定一个包含1到m之间正整数的数组queries，你需要按照以下规则处理所有queries[i]（从i=0到i=queries.length-1）：

  • 开始时，你有排列P=[1,2,3,…,m]。
  • 对于当前的i，找到queries[i]在排列P中的位置（从0开始索引），然后将这个数移动到排列P的开头。注意queries[i]在P中的位置就是queries[i]的结果。

返回包含给定查询结果的数组。

示例 1：

输入：queries = [3,1,2,1], m = 5
输出：[2,1,2,1]
解释：查询按如下方式处理：
对于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]

约束条件：

  • 1 <= m <= 10^3
  • 1 <= queries.length <= m
  • 1 <= queries[i] <= m

解题思路

解题思路

这道题有两种主要的解决思路：

方法一：模拟法（推荐）

直接按照题目要求模拟整个过程：

  1. 初始化排列P = [1,2,3,…,m]
  2. 对于每个查询queries[i]：
    • 在P中找到queries[i]的位置（线性搜索）
    • 记录该位置作为结果
    • 将该元素移动到数组开头

由于m的规模不大（≤1000），线性搜索和数组操作的开销都是可以接受的。

方法二：树状数组优化

对于更大规模的数据，可以使用树状数组来优化查找和更新操作，但考虑到题目约束条件，模拟法已经足够高效。

模拟法的实现比较直观：每次查询时遍历数组找到目标位置，然后使用erase和insert操作（或手动移动元素）来重新排列。这种方法代码简洁，易于理解和实现。

代码实现

class Solution {
public:
    vector<int> processQueries(vector<int>& queries, int m) {
        vector<int> P;
        for (int i = 1; i <= m; i++) {
            P.push_back(i);
        }
        
        vector<int> result;
        for (int query : queries) {
            int pos = find(P.begin(), P.end(), query) - P.begin();
            result.push_back(pos);
            
            P.erase(P.begin() + pos);
            P.insert(P.begin(), query);
        }
        
        return result;
    }
};

class Solution:
    def processQueries(self, queries: List[int], m: int) -> List[int]:
        P = list(range(1, m + 1))
        result = []
        
        for query in queries:
            pos = P.index(query)
            result.append(pos)
            
            P.pop(pos)
            P.insert(0, query)
        
        return result

public class Solution {
    public int[] ProcessQueries(int[] queries, int m) {
        List<int> P = new List<int>();
        for (int i = 1; i <= m; i++) {
            P.Add(i);
        }
        
        int[] result = new int[queries.Length];
        for (int i = 0; i < queries.Length; i++) {
            int pos = P.IndexOf(queries[i]);
            result[i] = pos;
            
            P.RemoveAt(pos);
            P.Insert(0, queries[i]);
        }
        
        return result;
    }
}

var processQueries = function(queries, m) {
    let P = [];
    for (let i = 1; i <= m; i++) {
        P.push(i);
    }
    
    let result = [];
    for (let query of queries) {
        let pos = P.indexOf(query);
        result.push(pos);
        
        P.splice(pos, 1);
        P.unshift(query);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型模拟法
时间复杂度O(n×m)
空间复杂度O(m)

其中n为查询次数，m为排列长度。每次查询需要O(m)时间进行搜索和移动操作。