1409. Queries on a Permutation With Key

题目信息

题号:

1409

难度:

Medium

主题:

数组、模拟、树状数组

原题:

LeetCode 1409

重点:

初始排列为 [1,2,...,m];每次记录查询值当前的零基下标,再把该值移动到排列最前端

题目重述

给定查询数组 queries 和正整数 m。初始维护排列 P = [1,2,...,m]。

依次处理每个查询值:把它在当前排列中的零基下标加入答案,然后从原位置移除并插入排列最前端。请返回所有查询得到的下标。

1 <= m <= 1000,1 <= queries.length <= m,1 <= queries[i] <= m。

自建示例

重复查询会立即命中排列首位:

输入:queries = [3,3,1], m = 4
输出:[2,0,1]
解释:首次查询 3 后排列变为 [3,1,2,4];第二次查询下标为 0;随后 1 的下标为 1。

排列只有一个元素时所有下标都为零:

输入:queries = [1], m = 1
输出:[0]
解释:唯一元素始终位于首位。