题目

题目来源：力扣（LeetCode）

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

一开始，排列 P=[1,2,3,…,m]。
对于当前的 i ，请你找出待查项 queries[i] 在排列 P 中的位置（下标从 0 开始），然后将其从原位置移动到排列 P 的起始位置（即下标为 0 处）。注意， queries[i] 在 P 中的位置就是 queries[i] 的查询结果。
请你以数组形式返回待查数组 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]

思路分析

模拟法

最容易想到的方法就是根据题目要求直接进行模拟。

对于数组 queries 中的每⼀个询问项 query，我们在排列 P 中找到 query 所在的位置，并把它加⼊ 答案。随后，我们需要将 query 移动到排列 P 的⾸部。具体地，我们⾸先将 query 从排列 P 中移 除，再添加到排列 P 的⾸部即可。

  1. /**
  2.  * @param {number[]} queries
  3.  * @param {number} m
  4.  * @return {number[]}
  5.  */
  6. var processQueries = function (queries, m) {
  7.   let ans = [], n = queries.length;
  9.   // 构建 p 排列的数组
  10.   let arrp = new Array(m).fill(0).map((v, k) => k + 1);
  12.   for (let i = 0; i < n; i++) {
  13.     let curr = queries[i];
  14.     let index = arrp.indexOf(curr);
  15.     ans.push(index);
  16.     arrp.splice(index, 1);
  17.     arrp.unshift(curr);
  18.   }
  20.   return ans;
  21. };

树状数组

  1. /**
  2.  * 树状数组
  3.  * @param len 数组长度
  4.  */
  5. function BIT(len) {
  6.   var arr = Array(len + 1).fill(0), lowbit = BIT.lowbit;
  7.   /**
  8.    * 查询数值x所处的位置
  9.    * @param {number} x 
  10.    */
  11.   this.query = function (x) {
  12.     let ret = 0;
  13.     while (x) {
  14.       ret += arr[x];
  15.       x -= lowbit(x);
  16.     }
  17.     return ret;
  18.   };
  19.   /**
  20.    * 将数值x移动dt位
  21.    * @param {*} x 
  22.    * @param {*} dt 
  23.    */
  24.   this.update = function (x, dt) {
  25.     while (x <= len) {
  26.       arr[x] += dt;
  27.       x += lowbit(x);
  28.     }
  29.   };
  30. }
  31. /**
  32. * 获取二进制最低位为1时对应的2的幂次方
  33. * @param {number} n 
  34. */
  35. BIT.lowbit = function (n) {
  36.   return (-n) & n;
  37. };
  39. /**
  40. * @param {number[]} queries
  41. * @param {number} m
  42. * @return {number[]}
  43. */
  44. var processQueries = function (queries, m) {
  45.   var n = queries.length, bit = new BIT(m + n), pos = [], rets = [];
  46.   for (let i = 1; i <= m; i++) {
  47.     pos[i] = n + i;
  48.     bit.update(n + i, 1);
  49.   }
  50.   for (let i = 0; i < n; i++) {
  51.     let query = queries[i], cur = pos[query];
  52.     bit.update(cur, -1);
  53.     rets.push(bit.query(cur));
  54.     cur = pos[query] = n - i;
  55.     bit.update(cur, 1);
  56.   }
  57.   return rets;
  58. };