侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 28 条评论

目 录CONTENT

文章目录

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

GabrielxD
2022-06-22 / 0 评论 / 0 点赞 / 337 阅读 / 1,052 字
温馨提示:
本文最后更新于 2022-07-27,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

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 个查询的答案定义如下:

  • 如果在时刻 timejindexj < nums.length,那么答案是此时的 nums[indexj]
  • 如果在时刻 timejindexj >= 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]

规律

条件 时间 原数组 动态长度
0t<n0 \le t < n tt [t,n1][t, n-1] ntn-t
n<t2nn < t \le 2n tt [0,tn1][0, t-n-1] tnt-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;
    }
}
0

评论区