题目
给你一个 下标从 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]
。
规律:
条件 | 时间 | 原数组 | 动态长度 |
---|---|---|---|
- 求出时间 t 处于前一半,还是后一半周期
- 如果处于前一半,需要转换成原数组的下标,才能找到对应元素。
- 如果处于后一半,不需要下标转换。
注意要判断下标是否超出动态数组长度。
代码
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;
}
}
评论区