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

链接：2672.有相同颜色的相邻元素数目
难度：Medium
标签：数组
简介：给你一个下标从 0 开始、长度为 n 的数组 nums 。请你返回一个长度与 queries 相等的数组 answer ，其中 answer[i]是前 i 个操作 之后 ，相邻元素颜色相同的数目。

题解 1 - python

• 编辑时间：2023-05-07
• 执行用时：276ms
• 内存消耗：47.6MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def colorTheArray(self, n: int, queries: List[List[int]]) -> List[int]:
        res = [0] * len(queries)
        list = [0] * n
        if n == 1:
            return res
        prev = 0
        for i in range(0, len(queries)):
            idx = queries[i][0]
            col = queries[i][1]
            if list[idx] != col:
                if idx != n - 1:
                    if list[idx] == 0:
                        if col == list[idx + 1]:
                            prev += 1
                    else:
                        if list[idx] == list[idx + 1]:
                            prev -= 1
                        elif col == list[idx + 1]:
                            prev += 1
                if idx != 0:
                    if list[idx] == 0:
                        if col == list[idx - 1]:
                            prev += 1
                    else:
                        if list[idx] == list[idx - 1]:
                            prev -= 1
                        elif col == list[idx - 1]:
                            prev += 1
            list[idx] = col
            res[i] = prev
        return res

题解 2 - rust

• 编辑时间：2023-05-07
• 执行用时：60ms
• 内存消耗：8.8MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn color_the_array(n: i32, queries: Vec<Vec<i32>>) -> Vec<i32> {
        let n = n as usize;
        let mut res = vec![0; queries.len()];
        let mut list = vec![0; n];
        if n != 1 {
            let mut prev = 0;
            for i in 0..queries.len() {
                let idx = queries[i][0] as usize;
                let col = queries[i][1];
                if list[idx] != col {
                    if idx != n - 1 {
                        if list[idx] == 0 {
                            if col == list[idx + 1] {
                                prev += 1;
                            }
                        } else {
                            if list[idx] == list[idx + 1] {
                                prev -= 1;
                            } else if col == list[idx + 1] {
                                prev += 1;
                            }
                        }
                    }
                    if idx != 0 {
                        if list[idx] == 0 {
                            if col == list[idx - 1] {
                                prev += 1;
                            }
                        } else {
                            if list[idx] == list[idx - 1] {
                                prev -= 1;
                            } else if col == list[idx - 1] {
                                prev += 1;
                            }
                        }
                    }
                }
                list[idx] = col;
                res[i] = prev;
            }
        }
        res
    }
}

题解 3 - cpp

• 编辑时间：2023-05-07
• 执行用时：452ms
• 内存消耗：197.9MB
• 编程语言：cpp
• 解法介绍：每次着色时统计对前后两个值得影响。

class Solution {
public:
    vector<int> colorTheArray(int n, vector<vector<int>>& queries) {
        vector<int> res(queries.size(), 0), list(n, 0);
        if (n == 1) return res;
        int prev = 0;
        for (int i = 0; i < queries.size(); i++) {
            int idx = queries[i][0], col = queries[i][1];
            if (list[idx] != col) {
                if (idx != n - 1) {
                    if (list[idx] == 0) {
                        if (col == list[idx + 1]) prev++;
                    } else {
                        if (list[idx] == list[idx + 1]) prev--;
                        else if (col == list[idx + 1]) prev++;
                    }
                }
                if (idx != 0) {
                    if (list[idx] == 0) {
                        if (col == list[idx - 1]) prev++;
                    } else {
                        if (list[idx] == list[idx - 1]) prev--;
                        else if (col == list[idx - 1]) prev++;
                    }
                }
            }
            list[idx] = col;
            res[i] = prev;
        }
        return res;
    }
};