1409.查询带键的排列

链接：1409.查询带键的排列
难度：Medium
标签：树状数组、数组、模拟
简介：给你一个待查数组 queries ，数组中的元素为 1 到 m 之间的正整数。 请你以数组形式返回待查数组 queries 的查询结果。

题解 1 - typescript

• 编辑时间：2021-11-14
• 执行用时：92ms
• 内存消耗：40.3MB
• 编程语言：typescript
• 解法介绍：链表。

class Data {
  next: Data | null;
  idx: number;
  val: number = -1;
}
function processQueries(queries: number[], m: number): number[] {
  const root = new Data();
  let p = root;
  for (let i = 1; i <= m; i++) {
    const item = new Data();
    item.idx = i - 1;
    item.val = i;
    p.next = item;
    p = item;
  }
  const ans: number[] = [];
  for (const query of queries) {
    p = root;
    while (p.next!.val !== query) {
      p = p.next!;
      p.idx++;
    }
    const node = p.next!;
    p.next = node.next;
    node.next = root.next;
    root.next = node;
    ans.push(node.idx);
    node.idx = 0;
  }
  return ans;
}

题解 2 - typescript

• 编辑时间：2021-11-14
• 执行用时：96ms
• 内存消耗：40.3MB
• 编程语言：typescript
• 解法介绍：树状数组。

class FenwickTree {
  arr: number[];
  constructor(private n: number) {
    this.arr = new Array(n + 1).fill(0);
  }
  add(idx: number, num: number): void {
    while (idx <= this.n) {
      this.arr[idx] += num;
      idx += this.lowbit(idx);
    }
  }
  at(idx: number): number {
    return this.query(idx) - this.query(idx - 1);
  }
  query(idx: number): number {
    let sum = 0;
    while (idx) {
      sum += this.arr[idx];
      idx -= this.lowbit(idx);
    }
    return sum;
  }
  private lowbit(num: number) {
    return num & -num;
  }
}
function processQueries(queries: number[], m: number): number[] {
  const n = queries.length;
  const tree = new FenwickTree(n + m);
  const idxList = new Array(m + 1).fill(0).map((_, i) => n + i);
  const ans: number[] = [];
  for (let i = 1; i <= m; i++) tree.add(i + n, 1);
  for (let i = 0; i < n; i++) {
    const query = queries[i];
    const idx = idxList[query];
    const cnt = tree.query(idx);
    ans.push(cnt - 1);
    tree.add(idx, -1);
    tree.add(n - i, 1);
    idxList[query] = n - i;
  }
  return ans;
}