统计奇数

[编程题]统计奇数

热度指数：101 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

长度为n的数组初始全为0，每分钟数组元素的值都会自增1。

m次操作，每次选择一个区间，在自增的基础上额外增1

求m次操作后数组中奇数的个数

示例1

输入

3,2,[1,2],[2,3]

输出

说明

第一分钟后 第一个数为2，第二个数为2，第三个数为1
第二分钟后 第一个数为3，第二个数为4，第三个数为3，一共两个数为奇数，所以输出2

备注:

函数共包含四个参数
第一个参数是一个int型参数n
第二个参数是一个int型参数m
第三个参数是一个共含有m个元素的vector<int>型参数l
第四个参数是一个共含有m个元素的vector<int>型参数r

算法知识视频讲解

Python 3

ZhongHaoWang

# 差分数组
class Solution:
    def oddnumber(self , n , m , l , r ):
        # write code here
        diff = [0] * (n + 1)
        for i in range(len(l)):
            diff[0] += 1
            diff[-1] -= 1
            diff[l[i] - 1] += 1
            diff[r[i]] -= 1
        ans = 0
        t = 0
        for i in range(len(diff) - 1):
            t += diff[i]
            if t & 1:
                ans += 1
        return ans

发表于 2021-08-27 18:39:10 回复(0)