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

English Version

题目描述

给定一个整数 n 表示一个长度为 n 的数组  colors，初始所有元素均为 0 ，表示是 未染色 的。同时给定一个二维整数数组 queries，其中 queries[i] = [indexi, colori]。对于第 i 个 查询：

• 将 colors[indexi] 染色为 colori。
• 统计 colors 中颜色相同的相邻对的数量（无论 colori）。

请你返回一个长度与 queries 相等的数组 answer ，其中 answer[i]是前 i 个操作的答案。

 

示例 1：

输入：n = 4, queries = [[0,2],[1,2],[3,1],[1,1],[2,1]]

输出：[0,1,1,0,2]

解释：

• 一开始 colors = [0,0,0,0]，其中 0 表示数组中未染色的元素。
• 在第 1 次查询后 colors = [2,0,0,0]。颜色相同的相邻对的数量是 0。
• 在第 2 次查询后 colors = [2,2,0,0]。颜色相同的相邻对的数量是 1。
• 在第 3 次查询后 colors = [2,2,0,1]。颜色相同的相邻对的数量是 1。
• 在第 4 次查询后 colors = [2,1,0,1]。颜色相同的相邻对的数量是 0。
• 在第 5 次查询后 colors = [2,1,1,1]。颜色相同的相邻对的数量是 2。

示例 2：

输入：n = 1, queries = [[0,100000]]

输出：[0]

解释：

在第一次查询后 colors = [100000]。颜色相同的相邻对的数量是 0。

 

提示：

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

解法

方法一

Python3

class Solution:
    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:
        nums = [0] * n
        ans = [0] * len(queries)
        x = 0
        for k, (i, c) in enumerate(queries):
            if i > 0 and nums[i] and nums[i - 1] == nums[i]:
                x -= 1
            if i < n - 1 and nums[i] and nums[i + 1] == nums[i]:
                x -= 1
            if i > 0 and nums[i - 1] == c:
                x += 1
            if i < n - 1 and nums[i + 1] == c:
                x += 1
            ans[k] = x
            nums[i] = c
        return ans

Java

class Solution {
    public int[] colorTheArray(int n, int[][] queries) {
        int m = queries.length;
        int[] nums = new int[n];
        int[] ans = new int[m];
        for (int k = 0, x = 0; k < m; ++k) {
            int i = queries[k][0], c = queries[k][1];
            if (i > 0 && nums[i] > 0 && nums[i - 1] == nums[i]) {
                --x;
            }
            if (i < n - 1 && nums[i] > 0 && nums[i + 1] == nums[i]) {
                --x;
            }
            if (i > 0 && nums[i - 1] == c) {
                ++x;
            }
            if (i < n - 1 && nums[i + 1] == c) {
                ++x;
            }
            ans[k] = x;
            nums[i] = c;
        }
        return ans;
    }
}

C++

class Solution {
public:
    vector<int> colorTheArray(int n, vector<vector<int>>& queries) {
        vector<int> nums(n);
        vector<int> ans;
        int x = 0;
        for (auto& q : queries) {
            int i = q[0], c = q[1];
            if (i > 0 && nums[i] > 0 && nums[i - 1] == nums[i]) {
                --x;
            }
            if (i < n - 1 && nums[i] > 0 && nums[i + 1] == nums[i]) {
                --x;
            }
            if (i > 0 && nums[i - 1] == c) {
                ++x;
            }
            if (i < n - 1 && nums[i + 1] == c) {
                ++x;
            }
            ans.push_back(x);
            nums[i] = c;
        }
        return ans;
    }
};

Go

func colorTheArray(n int, queries [][]int) (ans []int) {
	nums := make([]int, n)
	x := 0
	for _, q := range queries {
		i, c := q[0], q[1]
		if i > 0 && nums[i] > 0 && nums[i-1] == nums[i] {
			x--
		}
		if i < n-1 && nums[i] > 0 && nums[i+1] == nums[i] {
			x--
		}
		if i > 0 && nums[i-1] == c {
			x++
		}
		if i < n-1 && nums[i+1] == c {
			x++
		}
		ans = append(ans, x)
		nums[i] = c
	}
	return
}

TypeScript

function colorTheArray(n: number, queries: number[][]): number[] {
    const nums: number[] = new Array(n).fill(0);
    const ans: number[] = [];
    let x = 0;
    for (const [i, c] of queries) {
        if (i > 0 && nums[i] > 0 && nums[i - 1] == nums[i]) {
            --x;
        }
        if (i < n - 1 && nums[i] > 0 && nums[i + 1] == nums[i]) {
            --x;
        }
        if (i > 0 && nums[i - 1] == c) {
            ++x;
        }
        if (i < n - 1 && nums[i + 1] == c) {
            ++x;
        }
        ans.push(x);
        nums[i] = c;
    }
    return ans;
}