Java实现 LeetCode 561 数组拆分 I(通过排序算法改写PS:难搞)_leetcode java 数组拆分-程序员宅基地

技术标签: LeetCode  

561. 数组拆分 I

给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ,使得从1 到 n 的 min(ai, bi) 总和最大。

示例 1:

输入: [1,4,3,2]

输出: 4
解释: n 等于 2, 最大总和为 4 = min(1, 2) + min(3, 4).
提示:

n 是正整数,范围在 [1, 10000].
数组中的元素范围在 [-10000, 10000].
PS:

小编最近有点头晕,看来刷不了什么算法题了

class Solution {
    
     public int arrayPairSum(int[] nums) {
    
        boolean[] flag = new boolean[20001];
        int sum = 0;
        for (int v: nums) {
    
            flag[v + 10000] = !flag[v + 10000];
            sum += v;
        }

        int loss = 0;
        boolean searchFirst = true;
        int first = 0;
        for (int i = 0; i <= 20000; i++) {
    
            if (flag[i]) {
    
                if (searchFirst)
                    first = i;
                else
                    loss += i - first;
                
                searchFirst = !searchFirst;
            }
        }
        return (sum - loss) / 2;

    }
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/a1439775520/article/details/105127731

智能推荐

我学cocos2d-x (三) Node:一切可视化对象的祖先_cococs cocos2d::node 使用-程序员宅基地

文章浏览阅读1k次。在cocos2d-x中一切可视化的元素都集成自Node,zhe's_cococs cocos2d::node 使用

20180806 考试记录-程序员宅基地

文章浏览阅读74次。20180806 考试记录 T1 【NOIP2013模拟联考8】最短路(path)Solution设s为第0个标记点,t为k+1个跑k+1次最短路然后全排列暴力求解qwq注意最大值要设为long long范围最大值CodePS:各种修改qwq//By Menteur_Hxy#include&lt;queue&gt;#include..._i <= 3000000000u

DBA整理的万字详解MySQL性能优化,值得收藏!-程序员宅基地

文章浏览阅读190次。点击关注公众号,实用技术文章及时了解作者:LanceToBigDatacnblogs.com/zhangyinhua/p/7620964.html说起MySQL的查询优化,相信大家积累...

云开发(3)云函数本地调试_本地云函数调试并发数量限制-程序员宅基地

文章浏览阅读921次。云函数/云函数本地调试云函数是云开发其中一项基础能力,在云端运行的代码,微信私有协议天然鉴权,开发者只需编写自身业务逻辑代码。云函数个数免费版云函数数量上限为 50写完自己的原函数后,可以通过云函数的本地调试来进行调试,调试没有问题了就可以上传云端,对于解决bug查找bug是很好用的使用像调试自己的哪一个云函数就直接右键开启本地调试即可。就是这样一个页面此时运行自己的云函数就是在本地运行不是再云端给运行了。可以调试没问题后再传到云端,有时候会弹出一个错误解决方法:右键点击你_本地云函数调试并发数量限制

SQL创建默认值语句(CREATE DEFAULT)-程序员宅基地

文章浏览阅读5.8k次。微软的解释:创建称为默认值的对象。当绑定到列或别名数据类型时,如果插入时没有显式提供值,则默认值将指定一个值,以便将其插入该对象所绑定的列中(或者,如果是别名数据类型,则插入所有列中)。后续版本的 Microsoft SQL Server 将删除该功能。请避免在新的开发工作中使用该功能,并着手修改当前还在使用该功能的应用程序。语法 ..._sql declare default

Linux分区格式化实训操作说明_sdb7这个分区的具体含义-程序员宅基地

文章浏览阅读2.2k次。首先介绍一下背景知识:Linux主分区,扩展分区,逻辑分区的联系和区别Linux硬盘分区有三种,主磁盘分区、扩展磁盘分区、逻辑分区。一个硬盘主分区至少有1个,最多4个,扩展分区可以没有,最多1个。且主分区+扩展分区总共不能超过4个。逻辑分区可以有若干个。在linux下主分区和逻辑分区都可以用来放系统,引导os开机。分出主分区后,其余的部分可以分成扩展分区,一般情况是剩余磁盘空间全部配成扩展分区,..._sdb7这个分区的具体含义

随便推点

oracle9i打补丁,oracle11gr2打PSU补丁记录-程序员宅基地

文章浏览阅读72次。1、将数据库和监听程序关闭2、首先检查OPatch版本是否符合要求:$ORACLE_HOME/OPatch/opatch lsinventory3、若不符合要求,需先更新opatch:mv 掉原有的OPatch目录mv $ORACLE_HOME/OPatch $ORACLE_HOME/OPatchbakcp p6880880_112000_SOLARIS64-opatch11.2.0.3.12.z..._oracle9i 打补丁时ouihome设置

java ocr技术--tesseract-ocr:使用jTessBoxEditor制作训练库_jtessboxeditor训练英文和数字结合的图片-程序员宅基地

文章浏览阅读1.8k次,点赞4次,收藏18次。几个常见的问题:问题一:相关的几个软件下载地址Tesseract:Index of /tesseractjTessBoxEditor: VietOCR - Browse /jTessBoxEditor at SourceForge.net问题二:jTessBoxEditor下载是注意一下,中文的话要下载jTessBoxEditorFX问题三:mftraining执行时提示停止工作,一般是Tesseract版本的问题,可以选择Tesseract3验证过是好的,Tesser._jtessboxeditor训练英文和数字结合的图片

天平称重,进制转换解法_天平称重(进制解法) python-程序员宅基地

文章浏览阅读302次。题目:用天平称重时,我们希望用尽可能少的砝码组合称出尽可能多的重量。如果只有5个砝码,重量分别是1,3,9,27,81则它们可以组合称出1到121之间任意整数重量(砝码允许放在左右两个盘中)。本题目要求编程实现:对用户给定的重量,给出砝码组合方案。例如:用户输入:5程序输出:9-3-1用户输入:19程序输出:27-9+1要求程序输出的组合总是大数在前小数在后。可以假设用户的输入的数字符合范围1~121。思路:观察输出,都是3的多少次方,所以我们可以把输入的值,转换成3进制的_天平称重(进制解法) python

druid-1.1.21.jar-程序员宅基地

文章浏览阅读954次。链接:https://pan.baidu.com/s/1w5_GTiWuAR_X2t8J7JIP4Q提取码:a0u1_druid-1.1.21.jar

pthread_spinlock_t与pthread_mutex_t性能对比_pthread 性能 效率-程序员宅基地

文章浏览阅读8k次。看到一篇pthread_spinlock_t与pthread_mutex_t性能对比做的非常细致的博客,记录下来原文在此:http://www.cnblogs.com/diyunpeng/archive/2011/06/07/2074059.html_pthread 性能 效率

mysql innodb与myisam存储文件的区别-程序员宅基地

文章浏览阅读1.1k次。myisam:.frm: 存储表定义.myd(MYData):存储数据.MYI(MYindex):存储引擎innodb:.frm:存储表定义.idb:存储数据和索引,在同一个文件中_innodb和mylsam生成文件的区别