class Solution {
public:
vector<int> elementInNums(vector<int>& nums, vector<vector<int>>& queries) {
}
};
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 <= 1000 <= nums[i] <= 100n == queries.length1 <= n <= 105queries[j].length == 20 <= timej <= 1050 <= indexj < nums.length原站题解
golang 解法, 执行用时: 228 ms, 内存消耗: 16.8 MB, 提交时间: 2023-10-22 08:48:58
func elementInNums(nums []int, queries [][]int) []int {
n := len(nums)
ans := make([]int, len(queries))
for i, query := range queries {
time, index := query[0], query[1]
round := time / n
if round&1 == 1 {
end := time % n
if index >= end {
ans[i] = -1
} else {
ans[i] = nums[index]
}
} else {
start := time % n
if index+start >= n {
ans[i] = -1
} else {
ans[i] = nums[index+start]
}
}
}
return ans
}
java 解法, 执行用时: 5 ms, 内存消耗: 100.8 MB, 提交时间: 2023-10-22 08:48:27
class Solution {
public int[] elementInNums(int[] nums, int[][] queries){
int len = nums.length, n = queries.length;
int[] res = new int[n];
int T = 2 * len; // 周期
for (int i = 0; i < n; i++) {
int t = queries[i][0] % T; // 当前时间
if (t < len) { // 前一半
int idx = queries[i][1] + t; // 下标转换
res[i] = idx >= len ? - 1 : nums[idx];
} else { // 后一半
int idx = queries[i][1];
res[i] = idx >= (t - len) ? -1 : nums[idx];
}
}
return res;
}
}
cpp 解法, 执行用时: 312 ms, 内存消耗: 128.5 MB, 提交时间: 2023-10-22 08:48:06
class Solution {
public:
vector<int> elementInNums(vector<int>& nums, vector<vector<int>>& queries) {
int n = nums.size();
int nq = queries.size();
vector<int> res(nq, -1);
for (int i = 0; i < nq; ++i) {
int m = queries[i][0] % (n << 1);
if (m != n) {
int index = queries[i][1];
if (m < n && index < n-m) {
res[i] = nums[m + index];
} else if (m > n && index < m-n) {
res[i] = nums[index];
}
}
}
return res;
}
};
python3 解法, 执行用时: 160 ms, 内存消耗: 48.9 MB, 提交时间: 2023-10-22 08:47:32
class Solution:
def elementInNums(self, nums: List[int], queries: List[List[int]]) -> List[int]:
n = len(nums)
ans = [-1] * len(queries)
for i, (t, idx) in enumerate(queries):
t %= 2 * n
if t < n and idx < n - t:
ans[i] = nums[t + idx]
elif t > n and idx < t - n:
ans[i] = nums[idx]
return ans
python3 解法, 执行用时: 164 ms, 内存消耗: 45.9 MB, 提交时间: 2023-10-22 08:47:00
class Solution:
# 切片模拟
def elementInNums(self, nums: List[int], queries: List[List[int]]) -> List[int]:
n = len(nums)
states = []
for i in range(n):
states.append(nums[i:])
for i in range(n):
states.append(nums[:i])
res = []
for cycle, index in queries:
cycle %= len(states)
cand = states[cycle][index : index + 1]
res.append(cand[0] if cand else -1)
return res
# 找规律
def elementInNums2(self, nums: List[int], queries: List[List[int]]) -> List[int]:
"""
每过一分钟，数组的 最左边 的元素将被移除，直到数组为空。
然后，每过一分钟，数组的 尾部 将添加一个元素
"""
n = len(nums)
res = [-1] * len(queries)
for i, (time, pos) in enumerate(queries):
time %= 2 * n
if time < n and pos < n - time:
# 数组长度为 n-time ，查询 time + pos
res[i] = nums[time + pos]
elif time > n and pos < time - n:
# 数组长度为 time-n，查询 pos
res[i] = nums[pos]
return res