有相同颜色的相邻元素数目

标签: 数组

难度: Medium

给你一个下标从 0 开始、长度为 n 的数组 nums 。一开始，所有元素都是 未染色 （值为 0 ）的。

给你一个二维整数数组 queries ，其中 queries[i] = [indexi, colori] 。

对于每个操作，你需要将数组 nums 中下标为 indexi 的格子染色为 colori 。

请你返回一个长度与 queries 相等的数组 answer ，其中 answer[i]是前 i 个操作 之后 ，相邻元素颜色相同的数目。

更正式的，answer[i] 是执行完前 i 个操作后，0 <= j < n - 1 的下标 j 中，满足 nums[j] == nums[j + 1] 且 nums[j] != 0 的数目。

示例 1：

输入：n = 4, queries = [[0,2],[1,2],[3,1],[1,1],[2,1]]
输出：[0,1,1,0,2]
解释：一开始数组 nums = [0,0,0,0] ，0 表示数组中还没染色的元素。
- 第 1 个操作后，nums = [2,0,0,0] 。相邻元素颜色相同的数目为 0 。
- 第 2 个操作后，nums = [2,2,0,0] 。相邻元素颜色相同的数目为 1 。
- 第 3 个操作后，nums = [2,2,0,1] 。相邻元素颜色相同的数目为 1 。
- 第 4 个操作后，nums = [2,1,0,1] 。相邻元素颜色相同的数目为 0 。
- 第 5 个操作后，nums = [2,1,1,1] 。相邻元素颜色相同的数目为 2 。

示例 2：

输入：n = 1, queries = [[0,100000]]
输出：[0]
解释：一开始数组 nums = [0] ，0 表示数组中还没染色的元素。
- 第 1 个操作后，nums = [100000] 。相邻元素颜色相同的数目为 0 。

提示：

  • 1 <= n <= 105
  • 1 <= queries.length <= 105
  • queries[i].length == 2
  • 0 <= indexi <= n - 1
  • 1 <=  colori <= 105

Submission

运行时间: 159 ms

内存: 46.5 MB

class Solution:
    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:
        a = [0] * n
        cnt = 0
        ans = []
        for i, c in queries:
            if a[i]:
                if i and a[i] == a[i - 1]: cnt-=1
                if i < n - 1 and a[i] == a[i + 1]: cnt-=1 
            a[i] = c 
            if i and a[i] == a[i - 1]: cnt+=1
            if i < n - 1 and a[i] == a[i + 1]: cnt+=1 
            ans.append(cnt)
        return ans

Explain

该题解的核心思路是逐个处理查询，并更新数组 `nums` 的颜色。对于每个查询，首先检查当前位置的颜色是否已经设定，如果是的话，检查其与相邻元素的颜色是否相同，如果相同则减少相同颜色邻对的计数。然后更新当前位置的颜色，并再次检查该位置与其相邻元素的颜色是否相同，如果相同则增加相同颜色邻对的计数。每次操作后记录当前的相同颜色邻对数量。

时间复杂度: O(q)

空间复杂度: O(n)

class Solution:
    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:
        a = [0] * n  # 初始化长度为n的数组，所有元素初始颜色为0
        cnt = 0  # 初始化相同颜色相邻元素的计数器
        ans = []  # 用于存储每次查询后的结果
        for i, c in queries:  # 遍历每个查询指令
            if a[i]:  # 如果当前位置已经染过色
                if i and a[i] == a[i - 1]: cnt -= 1  # 如果当前颜色与前一个相同，减少计数
                if i < n - 1 and a[i] == a[i + 1]: cnt -= 1  # 如果当前颜色与后一个相同，减少计数
            a[i] = c  # 更新当前位置的颜色
            if i and a[i] == a[i - 1]: cnt += 1  # 如果新颜色与前一个相同，增加计数
            if i < n - 1 and a[i] == a[i + 1]: cnt += 1  # 如果新颜色与后一个相同，增加计数
            ans.append(cnt)  # 将当前计数加入结果列表
        return ans  # 返回结果列表

Explore

在题解中，对于位于数组第一个位置的元素（即索引为0的元素），它没有前一个元素，因此只需要检查其与后一个元素（索引为1的元素）的颜色是否相同。对于位于数组最后一个位置的元素（即索引为n-1的元素），它没有后一个元素，因此只需检查其与前一个元素（索引为n-2的元素）的颜色是否相同。这种边界检查通过条件语句'i and ...'及'i < n - 1 and ...'来实现，确保不会访问数组界外的元素。

题解中的算法并没有直接考虑原颜色与新颜色相同的情况。如果原颜色与新颜色相同，实际上并不需要进行计数的调整，因为颜色没有变化，相邻元素的颜色关系也没有改变。优化这部分可以在设置新颜色前先检查新颜色是否与原颜色相同，如果相同，则不进行任何计数调整，也不更新颜色，直接继续到下一个查询，这样可以减少不必要的操作。

对于本题的具体需求，使用数组a是非常合适的，因为数组提供了O(1)时间复杂度的随机访问能力，这对于频繁的颜色更新和检查操作是非常高效的。尽管如此，在某些变化的场景下，例如如果数组非常大且大部分元素未被频繁更新或查询，可以考虑使用哈希表来记录已经修改过颜色的元素位置及其颜色，这样可以节省空间，尤其是在稀疏更新的情况下。

是的，如果queries数组中存在重复的颜色指令，题解中的算法会进行不必要的操作，因为重新染相同颜色并不改变任何颜色关系，也不应该影响计数。可以优化这一点，通过在更新颜色之前检查即将应用的颜色是否与当前位置的颜色相同。如果相同，则跳过当前操作，直接记录当前计数到结果列表中，这样可以避免多余的计数调整和颜色更新。