LeetCode-2529题:正整数和负整数的最大计数(原创)

【题目描述】

    给你一个按 非递减顺序 排列的数组 nums ,返回正整数数目和负整数数目中的最大值。换句话讲,如果 nums 中正整数的数目是 pos ,而负整数的数目是 neg ,返回 pos 和 neg二者中的最大值。注意:0 既不是正整数也不是负整数。

示例 1:

输入:nums = [-2,-1,-1,1,2,3]
输出:3
解释:共有 3 个正整数和 3 个负整数。计数得到的最大值是 3 。

示例 2:

输入:nums = [-3,-2,-1,0,0,1,2]
输出:3
解释:共有 2 个正整数和 3 个负整数。计数得到的最大值是 3 。
示例 3:

输入:nums = [5,20,66,1314]
输出:4
解释:共有 4 个正整数和 0 个负整数。计数得到的最大值是 4 。
提示:

1 <= nums.length <= 2000
-2000 <= nums[i] <= 2000
nums 按 非递减顺序 排列。

【题目链接】. - 力扣(LeetCode)

【解题代码】

package array;

public class MaximumCount {

    public static void main(String[] args) {
        //int[] nums = new int[]{-2, -1, -1, 1, 2, 3};
        int[] nums = new int[]{-3, -2, -1, 0, 0, 1, 2};
        //int[] nums = new int[]{5, 20, 66, 1314};
        long start = System.currentTimeMillis();
        int result = new MaximumCount().maximumCount(nums);
        System.out.println("函数运行时间:" + (System.currentTimeMillis() - start) + "MS");
        System.out.println("函数运行结果:" + result);
    }

    public int maximumCount(int[] nums) {
        int i = 0, j = nums.length - 1;
        while (i <= j) {
            int n =  i + (j - i) / 2;
            if (nums[n] < 0) {
                i = n + 1;
            } else { 
                j = n - 1;
            }
        }
        while (i < nums.length && nums[i] == 0) {
            i++;
        }
        return Math.max(j + 1, nums.length - i);
    }
}

【解题思路】

        拿到题目,分析一下,感觉可以类似二分检索的方式:设置首尾两个索引值i,j,如果中间索引n值小于0,那么将i设置为n+1,否则(n值大于等于0)将j设置为n-1,循环结束后,索引j及之前的数据应该都是小于0的值,索引i及之后的数据都是大于等于0的数。再将i跳过之后等于0的数值即可。按照这个思路,很快完成代码编写,并提交成功

【解题步骤】

  1. 采用二分查找算法,首先定义首尾索引两个变量;
     int i = 0, j = nums.length - 1;
  2. 二分查找算法的终止条件,索引值i大于等于索引值j
    while (i <= j) {
  3. 获取索引值i和j中间索引值n
    int n =  i + (j - i) / 2;
  4. 如果nums[n]小于0,那么将i设置为n + 1,如果nums[n]大于等于0,那么将j设置为n - 1
    if (nums[n] < 0) {
        i = n + 1;
    } else { // 如果nums[n]大于等于0,那么将j设置为n - 1
        j = n - 1;
    }
  5. 循环结束后,向后跳过所有等于0的数值
    while (i < nums.length && nums[i] == 0) {
        i++;
    }
  6. 负数的数量等于j+1, 正数的数量等于nums.length - i,取两者最大值
    return Math.max(j + 1, nums.length - i);

【思考总结】

  1. 二分查找算法定义:二分查找算法(英语:binary search algorithm),也称折半搜索算法是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。二分查找算法在最坏情况下是对数时间复杂度的,需要进行log⁡n次比较操作
  2. 按照大神Donald Knuth所说“思路很简单,细节是魔鬼”,二分查找算法需要特别关注中间索引值这些细节方面。比如如果写成“int n =  (i + j) / 2;” ,可能会存在溢出的bug,第一篇二分搜索论文是 1946 年发表,然而第一个没有 bug 的二分查找法却是在 1962 年才出现,中间用了 16 年的时间。
  3. 对于二分查找等经典算法,要学会灵活运用,根据实际情况进行调整
  4. LeetCode解题之前,一定不要看题解,看了就“破功”了! 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/537078.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

windows ffmpeg7 通过rtsp拉取h265裸流

点击下边那个链接会转到github 下载完成后&#xff0c;添加include、lib到工程。 添加头文件&#xff1a; extern "C" { #include "libavcodec/avcodec.h" #include "libavformat/avformat.h" #include "libavformat/avio.h" #inclu…

【实战JVM】打破双亲委派机制之自定义类加载器

个人名片&#xff1a; &#x1f43c;作者简介&#xff1a;一名大三在校生&#xff0c;喜欢AI编程&#x1f38b; &#x1f43b;‍❄️个人主页&#x1f947;&#xff1a;落798. &#x1f43c;个人WeChat&#xff1a;hmmwx53 &#x1f54a;️系列专栏&#xff1a;&#x1f5bc;️…

JVS智能BI:嵌套数据集在多层次数据关联中的实战应用

在数据分析平台中&#xff0c;数据集的嵌套调用主要用于处理复杂数据结构或多层次数据关联&#xff0c;或者有多场景使用的重复使用中间数据&#xff0c;那么就需要把某些数据生成中间结果的数据集合。 例如&#xff1a;用户的分类需要根据用户的各方面的数据特征进行分类打标…

算法设计与分析实验报告c++实现(矩阵链相乘问题、投资问题、背包问题、TSP问题、数字三角形)

一、实验目的 1&#xff0e;加深学生对动态规划算法设计方法的基本思想、基本步骤、基本方法的理解与掌握&#xff1b; 2&#xff0e;提高学生利用课堂所学知识解决实际问题的能力&#xff1b; 3&#xff0e;提高学生综合应用所学知识解决实际问题的能力。 二、实验任务 1、…

自动化测试提速必备 - 并发编程

在自动化测试领域&#xff0c;多线程和多进程技术被广泛应用于提高测试的执行效率和性能。通过并发运行测试用例&#xff0c;可以显著缩短测试周期&#xff0c;特别是在面对大量测试用例或者需要在多个环境中进行测试时尤为重要。 在实际的自动化测试中&#xff0c;我们经常碰…

2024年【T电梯修理】考试总结及T电梯修理考试技巧

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 T电梯修理考试总结考前必练&#xff01;安全生产模拟考试一点通每个月更新T电梯修理考试技巧题目及答案&#xff01;多做几遍&#xff0c;其实通过T电梯修理试题及解析很简单。 1、【多选题】修理工陶、陈&#xff0c…

废石颗粒运动理论模型及Python模拟

学者赵国彦等[26]对于废石颗粒运动的理论模型进行做了较为充分的研究&#xff0c;本文在以往研究的基础上对相关推导进行补充修正&#xff0c;并以某金矿充填废石的基本物理性能测试数据为基础&#xff0c;对废石运动理论模型的进行模拟。 4.2.1废石运动理论模型 4.2.1.1废石…

AI大模型探索之路-应用篇10:Langchain框架-架构核心洞察

目录 前言 一、LangChain设计目标 二、LangChain设计之道 三、LangChain典型应用 1、简单的问答Q&A over SQL CSV: 2、聊天机器人Chatbots: 3、总结摘要Summarization: 4、网页爬虫Web scraping: 5、本地知识库&#xff08;Q&A with RAG): 三、LangChain架构…

数字阅览室-数字图书馆体系的重要补充

数字阅览室&#xff08;Digital Reading Room&#xff09;是一种依托现代信息技术&#xff0c;特别是互联网、数字媒体技术和数据库管理技术&#xff0c;为用户提供在线访问、阅读、学习和研究各类数字化文献资源的虚拟空间。它是数字图书馆服务体系中的一个重要组成部分&#…

文库配置异步转换(宝塔)| 魔众文库系统

执行以下操作前提前进入网站根目录&#xff0c;如 cd /www/wwwroot/example.com执行 artisan 命令前请参照 开发教程 → 开发使用常见问题 → 如何运行 /www/server/php/xxx/bin/php artisan xxx 命令 步骤1&#xff0c;生成数据库队列表迁移文件 在执行该步骤前&#xff0c;请…

数据可视化高级技术Echarts(折线图)

目录 一、什么是折线图 二、如何实现 1.基本折线图 2.如何变得平滑只需要定义&#xff1a; smooth 3.如何定义线条的样式 color&#xff1a;设置线的颜色 width&#xff1a;设置线宽 type&#xff1a;设置线的类型 4.如何定义节点样式 symbol symbolSize&#xff1a…

开发着开发着,盘满了

办公电脑突然报家目录不足1G空间了, 使用 Disk Usage Analyzer 工具打开看了下, 微软还真没把我当穷人, 一个vs code给我占了30几个G的空间. 大家可能也遇到这种情况的, 看到真的让人窒息, 以前windows上被VS studio 支配C盘的感觉又回来了. 不过这个ubuntu好处理点, 我该删…

算法打卡day32

今日任务&#xff1a; 1&#xff09;738.单调递增的数字 2&#xff09;968.监控二叉树 738.单调递增的数字 题目链接&#xff1a;738. 单调递增的数字 - 力扣&#xff08;LeetCode&#xff09; 文章讲解&#xff1a;代码随想录 (programmercarl.com) 视频讲解&#xff1a;贪…

CPU核心数、线程数都是什么意思?

最早&#xff0c;每个物理 cpu 上只有一个核心&#xff0c;对操作系统而言&#xff0c;也就是同一时刻只能运行一个进程/线程。 为了提高性能&#xff0c;cpu 厂商开始在单个物理 cpu 上增加核心&#xff08;实实在在的硬件存在&#xff09;&#xff0c;也就出现了多核 cpu&…

个人博客项目笔记_07

写文章 写文章需要 三个接口&#xff1a; 获取所有文章类别 获取所有标签 发布文章 1. 所有文章分类 1.1 接口说明 接口url&#xff1a;/categorys 请求方式&#xff1a;GET 请求参数&#xff1a; 参数名称参数类型说明 返回数据&#xff1a; {"success":…

Linux启动流程,常见故障英文总结/Linux学习环境发行版本选择及运行故障(补充)

小编这里对前面文章内容进行补充 1.运维架构人员理解Linux启动流程&#xff08;对故障进行排查&#xff09;&#xff0c;企业面试面试官让面试者描述Linux启动细节&#xff0c;小编在这篇文章补充以下&#xff0c;制作了图表&#xff0c;有利于大家看懂整个流程 2.对于初学者/老…

14亿美元!德国默克与AI生物科技公司合作;马斯克Neuralink首位脑机接口植入者用意念打游戏;黄仁勋在俄勒冈州立大学开讲

AI for Science 的新成果、新动态、新视角—— 日本第一 IT 公司富士通&#xff1a;生成式 AI 加速药物研发 马斯克&#xff1a;Neuralink 首位脑机接口植入者用「意念」打游戏 默克与 AI 生物科技公司 Caris 达成合作 AI 蛋白质设计服务提供商「天鹜科技」完成数千万元 Pre…

IDEA中使用正则表达式替换时间日期

很多时候需要把系统中的时间替换成当前时间&#xff0c;这是后我们就可以把数据库SQL文件在IDEA中打开&#xff0c;然后使用正则进行替换&#xff0c;下面我们来看下&#xff1a; 1.日期格式&#xff1a;校验yyyy&#xff0d;MM&#xff0d;dd ((([0-9]{3}[1-9]|[0-9]{2}[1-9…

ELK 企业级日志分析 ELFK

一 ELK 简介 ELK平台是一套完整的日志集中处理解决方案&#xff0c;将 ElasticSearch、Logstash 和 Kiabana 三个开源 工具配合使用&#xff0c; 完成更强大的用户对日志的查询、排序、统计需求。 1 ElasticSearch&#xff1a; 是基于Lucene&#xff08;一个全文检索引擎的…

golang的引用和非引用总结

目录 概述 一、基本概念 指针类型&#xff08;Pointer type&#xff09; 非引用类型&#xff08;值类型&#xff09; 引用类型&#xff08;Reference Types&#xff09; 解引用&#xff08;dereference&#xff09; 二、引用类型和非引用类型的区别 三、golang数据类型…