Question

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

English Version

题目描述

给你一个 下标从 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 <= 105
• queries[j].length == 2
• 0 <= timej <= 105
• 0 <= indexj < nums.length

解法

方法一：直接计算

我们先初始化一个数组 $ans$，长度为 $m$，用于存储答案，初始化所有元素为 $-1$。

接下来遍历数组 $queries$，对于每个查询，我们先获取当前查询的时间 $t$ 和索引 $i$，先将 $t$ 对 $2n$ 取模，然后判断 $t$ 和 $n$ 的关系：

• 如果 $t \lt n$，那么 $t$ 时刻的数组元素个数为 $n - t$，并且数组元素是原数组元素整体向左移动 $t$ 个位置后的结果，因此如果 $i \lt n - t$，答案为 $nums[i + t]$；
• 如果 $t \gt n$，那么 $t$ 时刻的数组元素个数为 $t - n$，并且数组元素是原数组元素的前 $t - n$ 个元素，因此如果 $i \lt t - n$，答案为 $nums[i]$。

最后返回数组 $ans$ 即可。

时间复杂度 $O(m)$，其中 $m$ 为数组 $queries$ 的长度。忽略答案数组的空间消耗，空间复杂度 $O(1)$。

class Solution:
  def elementInNums(self, nums: List[int], queries: List[List[int]]) -> List[int]:
    n, m = len(nums), len(queries)
    ans = [-1] * m
    for j, (t, i) in enumerate(queries):
      t %= 2 * n
      if t < n and i < n - t:
        ans[j] = nums[i + t]
      elif t > n and i < t - n:
        ans[j] = nums[i]
    return ans

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

class Solution {
public:
  vector<int> elementInNums(vector<int>& nums, vector<vector<int>>& queries) {
    int n = nums.size(), m = queries.size();
    vector<int> ans(m, -1);
    for (int j = 0; j < m; ++j) {
      int t = queries[j][0], i = queries[j][1];
      t %= (n * 2);
      if (t < n && i < n - t) {
        ans[j] = nums[i + t];
      } else if (t > n && i < t - n) {
        ans[j] = nums[i];
      }
    }
    return ans;
  }
};

func elementInNums(nums []int, queries [][]int) []int {
  n, m := len(nums), len(queries)
  ans := make([]int, m)
  for j, q := range queries {
    t, i := q[0], q[1]
    t %= (n * 2)
    ans[j] = -1
    if t < n && i < n-t {
      ans[j] = nums[i+t]
    } else if t > n && i < t-n {
      ans[j] = nums[i]
    }
  }
  return ans
}