统计有序矩阵中的负数

devtools/2025/1/15 18:35:25/

统计有序矩阵中的负数

描述

给你一个 m * n矩阵 grid矩阵中的元素无论是按行还是按列,都以非递增顺序排列。

请你统计并返回 grid负数 的数目

示例 1:
输入:grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
输出:8
解释:矩阵中共有 8 个负数。示例 2:
输入:grid = [[3,2],[1,0]]
输出:0示例 3:
输入:grid = [[1,-1],[-1,-1]]
输出:3示例 4:
输入:grid = [[-1]]
输出:1

代码

最简单的就是暴力破解,但是这个因为有序,所以当我们找到是负数的时候,直接后面可以不判断了

class Solution(object):def countNegatives(self, grid):count = 0for i in range(len(grid)):for j in range(len(grid[0])):if grid[i][j] < 0:count += len(grid[0]) - jbreakreturn count

当然因为是不递增的,我们还可以想到使用二分查找法,时间复杂度是 O(logn)

class Solution(object):def getIndex(self, line):lineLen = len(line)left = 0right = lineLen - 1while left <= right:mid = (left + right) // 2if line[mid] < 0 and ((mid != 0 and line[mid -1] >= 0) or (mid == 0)):return lineLen - midelif line[mid] < 0:right = mid -1else:left = mid + 1return 0def countNegatives(self, grid):count = 0for i in range(len(grid)):        count += self.getIndex(grid[i])return count

http://www.ppmy.cn/devtools/150742.html

相关文章

电商系统,核心通用架构案例设计方案浅析

文章目录 一、用户系统案例设计1、用户信息的存储方案2、用户注册确保唯一3、用户数据合并方案4、用户敏感信息加密存储5、数据传输安全性6、多用户数据隔离性7、防止恶意注册8、用户好友关系存储方案9、用户登录token方案10、会员优先处理设计 二、网关系统设计1、网关的功能2…

Oracle 学习指南与资料分享

Oracle 学习资料 Oracle 学习资料 Oracle 学习资料 在当今数字化飞速发展的浪潮中&#xff0c;Oracle 数据库凭借其卓越的性能、强大的功能以及高度的可靠性&#xff0c;稳坐数据库领域的前沿宝座&#xff0c;广泛应用于金融、电信、航空航天等诸多关键行业。如果你有志于深入…

C++ Primer Plus第五章笔记《循环和关系表达式》

这里的笔记区别于精简基础&#xff0c;会记录较多C的细节 文章目录 前言一、for循环1.1 for循环的组成部分关系表达式判断情况 1.2 回到for循环1.3 修改步长1.4 使用for循环访问字符串1.5 递增运算符&#xff08;&#xff09;和递减运算符&#xff08;- -&#xff09;1.6 副作用…

【系统安全】CVE-2024-49113 Windows轻量级目录访问协议(LDAP)拒绝服务漏洞

文章目录 免责声明一、漏洞描述二、漏洞成因三、漏洞危害四、影响版本五、攻击流程六、修复方案 免责声明 在网络安全领域&#xff0c;技术文章应谨慎使用&#xff0c;遵守法律法规&#xff0c;严禁非法网络活动。未经授权&#xff0c;不得利用文中信息进行入侵&#xff0c;造…

《AI赋能鸿蒙Next,打造极致沉浸感游戏》

在游戏开发领域&#xff0c;鸿蒙Next系统与人工智能技术的结合为开发者们带来了前所未有的机遇&#xff0c;使打造更具沉浸感的游戏成为可能。以下将深入探讨如何利用人工智能在鸿蒙Next上开发出令人身临其境的游戏。 利用AI优化游戏角色智能行为 在传统游戏中&#xff0c;非…

美摄科技PC端视频编辑解决方案,为企业打造专属的高效创作平台

在当今这个信息爆炸的时代&#xff0c;视频已成为不可或缺的重要内容形式&#xff0c;美摄科技推出了PC端视频编辑解决方案的私有化部署服务&#xff0c;旨在为企业提供一款量身定制的高效创作平台。 一、全面功能&#xff0c;满足企业多样化需求 美摄科技的PC端视频编辑解决…

1 XDMA IP介绍

1 XDMA IP介绍 关于XDMA IP介绍的介绍无非就是参考手册&#xff0c;我也看了一些手册&#xff0c;对于特定型号的IP其配置页面大差不差&#xff0c;代表的意思也是大差不差&#xff0c;所以在IP核介绍这里&#xff0c;就推荐大佬的文章&#xff0c;这个文章也是我的入门的文章…

宝塔安装mongodb后,写脚本监控运行状态,关闭后自动重启

最近项目用上了mongodb&#xff0c;但是每天晚上 mongodb都回自动关闭&#xff0c;没办法 只能写个监视服务的脚本 在关闭的话就直接重启&#xff0c;创建个计划任务&#xff0c;每三分钟执行一次 # 检查mongo是否还在进程中 countps aux|grep mongo| grep -v grep |wc -l echo…