leetcode
leetcode 1851 ~ 1900
查询删除和添加元素后的数组

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

难度:

标签:

题目描述

代码结果

运行时间: 142 ms, 内存: 44.5 MB


/*
 * LeetCode 2113: Queries on an Array After Removing and Adding Elements
 * 
 * 思路:
 * 1. 使用 Java Stream 来处理每个查询。
 * 2. 'remove' 查询会从数组中删除指定的元素。
 * 3. 'add' 查询会在数组末尾添加指定的元素。
 * 4. 'get' 查询会返回当前数组中的元素列表。
 */
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

public class Solution {
    public List<Integer> processQueries(List<List<String>> queries) {
        List<Integer> array = new ArrayList<>();
        
        List<Integer> result = queries.stream()
            .flatMap(query -> {
                String command = query.get(0);
                if (command.equals("add")) {
                    int value = Integer.parseInt(query.get(1));
                    array.add(value);
                } else if (command.equals("remove")) {
                    int value = Integer.parseInt(query.get(1));
                    array.remove(Integer.valueOf(value));
                } else if (command.equals("get")) {
                    return array.stream();
                }
                return array.stream();
            })
            .collect(Collectors.toList());

        return result;
    }
}

解释

方法:

这道题目的核心是模拟数组在一系列操作后的状态。这里的操作包括添加和删除元素,但是具体的添加和删除规则并没有明确说明。基于题解代码,我们可以推测操作是周期性的,周期长度为2m(m是数组初始长度)。在前m个时间单位,数组长度递减,之后的m个时间单位,数组长度递增。查询操作是确定在特定时间点给定索引位置的元素。如果索引有效,则返回该位置的元素;如果无效(索引超出当前数组长度),则返回-1。\n\n1. 对于每个查询,计算时间点和索引。\n2. 使用time % (2 * m)确保处理的时间在合法范围内(即0到2m-1)。\n3. 计算当前时间的数组长度。\n4. 判断索引是否在当前数组长度内。如果在,计算并确定该索引在原始数组中的位置;如果不在,返回-1。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
在此算法中,如何确保每次计算的`lengthAtTime`正确反映了删除或添加操作后数组的实际长度?
算法中,`lengthAtTime` 的计算依赖于时间 `time` 和数组最初长度 `m` 的关系。通过 `lengthAtTime = abs(m - time)`,在周期的前半部分(即 `time < m` 时),数组长度从 `m` 减少到 `0`;而在周期的后半部分(即 `time >= m` 时),数组长度则从 `0` 增加回 `m`。这种计算方式利用了绝对值函数的性质来模拟数组长度的周期性增减,确保每次计算反映的是删除或添加后的实际数组长度。
🦆
为什么在计算`time`时使用`time % (2 * m)`,这样的周期性处理对算法的正确性有什么关键作用?
使用 `time % (2 * m)` 是为了将时间限制在一个固定的周期内,这里的周期长度为 `2m`,代表一个完整的增减周期。在此周期内,数组长度先减少再增加。这样的处理确保无论查询的时间点多久远,我们总能将其映射回这个固定的周期内,从而正确模拟数组长度的变化。这对于算法模拟周期性变化的数组状态是必要的,确保无论何时进行查询,都能得到正确的结果。
🦆
如果数组的操作规则不是简单的周期增减,算法需要做哪些调整来适应更复杂的操作规则?
如果数组的操作规则更加复杂,例如不同时间段有不同的添加或删除模式,算法需要进行适应性的调整。首先,可能需要一个更复杂的函数或数据结构来记录每个时间点数组的状态或长度变化。其次,查询处理也需要根据这些记录的状态动态调整,以确保能够准确地反映出任何给定时间点的数组长度和内容。此外,可能还需要修改周期性处理的逻辑,以适应非周期性或不规则周期性的变化模式。
🦆
在处理查询结果时,算法如何处理数组长度在减少到0之后再次增加的情况?
在算法中,数组长度的减少到0然后再增加是通过计算 `lengthAtTime = abs(m - time)` 实现的。在周期的前半部分,长度逐渐减少至0(当 `time` 接近 `m` 时)。一旦 `time` 超过 `m`,`abs(m - time)` 会使得长度从0开始逐步增加。这种处理方式确保在数组长度减至0后,随着时间的推移,数组的长度能够正确地重新增加。因此,无论查询发生在减少阶段还是增加阶段,算法都能根据当前 `time` 计算出正确的数组长度,并据此处理查询结果。

相关问题