1409. Queries on a Permutation With Key¶
题目信息¶
- 题号:
1409
- 难度:
Medium
- 主题:
数组、模拟、树状数组
- 原题:
- 重点:
初始排列为
[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]
解释:唯一元素始终位于首位。