【迭代, 数学】查询删除和添加元素后的数组

题目

2113. 查询删除和添加元素后的数组

---

给你一个 下标从 0 开始 的数组 nums。一开始，在第 0 分钟，数组没有变化。此后每过一分钟，数组的 最左边 的元素将被移除，直到数组为空。然后，每过一分钟，数组的 尾部 将添加一个元素，添加的顺序和删除的顺序相同，直到数组被复原。此后上述操作无限循环进行。

• 举个例子，如果 nums = [0, 1, 2]，那么数组将按如下流程变化：[0,1,2] → [1,2] → [2] → [] → [0] → [0,1] → [0,1,2] → [1,2] → [2] → [] → [0] → [0,1] → [0,1,2] → ...

然后给你一个长度为 n 的二维数组 queries，其中 queries[j] = [timej, indexj]，表示第 j 个查询。第 j 个查询的答案定义如下：

• 如果在时刻 timej，indexj < nums.length，那么答案是此时的 nums[indexj]；
• 如果在时刻 timej，indexj >= nums.length，那么答案是 -1。

请返回一个长度为 n 的整数数组 ans，其中 ans[j] 为第 j 个查询的答案。

示例 1:

输入: nums = [0,1,2], queries = [[0,2],[2,0],[3,2],[5,0]]
输出: [2,2,-1,0]
解释:
第 0 分钟: [0,1,2] - 数组和 nums 相同。
第 1 分钟: [1,2]   - 最左侧元素 0 被移除。
第 2 分钟: [2]     - 最左侧元素 1 被移除。
第 3 分钟: []      - 最左侧元素 0 被移除。
第 4 分钟: [0]     - 0 被添加到数组尾部。
第 5 分钟: [0,1]   - 1 被添加到数组尾部。

在第 0 分钟, nums[2] 是 2。
在第 2 分钟, nums[0] 是 2。
在第 3 分钟, nums[2] 不存在。
在第 5 分钟, nums[0] 是 0。

示例 2:

输入: nums = [2], queries = [[0,0],[1,0],[2,0],[3,0]]
输出: [2,-1,2,-1]
第 0 分钟: [2] - 数组和 nums 相同。
第 1 分钟: []  - 最左侧元素 2 被移除。
第 2 分钟: [2] - 2 被添加到数组尾部。
第 3 分钟: []  - 最左侧元素 2 被移除。

在第 0 分钟, nums[0] 是 2。
在第 1 分钟, nums[0] 不存在。
在第 2 分钟, nums[0] 是 2。
在第 3 分钟, nums[0] 不存在。

提示:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100
• n == queries.length
• 1 <= n <= 10^5
• queries[j].length == 2
• 0 <= timej <= 10^5
• 0 <= indexj < nums.length

解题

方法一：迭代 数学

思路

找规律，假如有一个数组为 `[1, 2, 3, …, n-1]，根据题意：

时间	数组	长度
0	[0, 1, 2, 3, ..., n-1]	n
1	[ 1, 2, 3, ..., n-1]	n - 1
2	[ 2, 3, ..., n-1]	n - 2
3	[ 3, ..., n-1]	n - 3
…	…	…
n	[ ]	0
n + 1	[0 ]	1
n + 2	[0, 1 ]	2
n + 3	[0, 1, 2 ]	3

易得：数组的内容以及长度在以 2n 为一个周期循环地变化着。

前一半周期里，时间为 t 时，原数组范围 [t, n-1], 动态数组对应的下标范围 [0, n-1-t]。
后一半周期里，时间为 t 时，原数组和动态数组的下标范围都是 [0, t-n-1]。

规律：

条件	时间	原数组	动态长度
$0 \le t < n$	$t$	$[t, n-1]$	$n-t$
$n < t \le 2n$	$t$	$[0, t-n-1]$	$t-n$

1. 求出时间 t 处于前一半，还是后一半周期
2. 如果处于前一半，需要转换成原数组的下标，才能找到对应元素。
3. 如果处于后一半，不需要下标转换。

注意要判断下标是否超出动态数组长度。

代码

class Solution {
    public int[] elementInNums(int[] nums, int[][] queries) {
        int n = nums.length, m = queries.length;
        int[] ans = new int[m];
        int T = 2 * n;
        for (int i = 0; i < m; i++) {
            int[] query = queries[i];
            int t = query[0] % T;
            if (t < n) {
                int idx = query[1] + t;
                ans[i] = idx >= n ? - 1 : nums[idx];
            } else {
                int idx = query[1];
                ans[i] = idx >= (t - n) ? -1 : nums[idx];
            }
        }
        return ans;
    }
}