java分割一个整数数组,力扣算法-561.数组拆分-数组-java

力扣算法-561.数组拆分-数组-java

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

返回该 最大总和

示例 1：

输入：nums = [1,4,3,2]

输出：4

解释：所有可能的分法(忽略元素顺序)为：

(1, 4), (2, 3) - min(1, 4) + min(2, 3) = 1 + 2 = 3

(1, 3), (2, 4) - min(1, 3) + min(2, 4) = 1 + 2 = 3

(1, 2), (3, 4) - min(1, 2) + min(3, 4) = 1 + 3 = 4

所以最大总和为 4

示例 2：

输入：nums = [6,2,6,5,1,2]

输出：9

解释：最优的分法为 (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9

提示：

1 = n = 10^4

nums.length == 2 * n

-10^4 = nums[i] = 10^4

思路：该题明显需要进行排序，先进行排序，然后将索引为奇数的元素值求和，即为答案

思路一、时间复杂度O(NlogN)

代码：

public static int arrayPairSum(int[] nums)

{

Arrays.sort(nums);

int res = 0;

for(int i = 0;i nums.length;i+=2)

{

res += nums[i];

}

return res;

}

思路二：官方解答，时间复杂度O(N),该方式是规定了一个大数组count[20001],count数组索引对应数值-10000~10000,即count[i]对应的数为i-10000(因为有负数)，然后遍历nums，将count中nums[i]下标的值count[nums[i]]++;这样就用count数组中count0的值记录了nums中的值，然后遍历count，将count中0对应的下标赋值给nums数组，这样的出来的nums数组就是排好序的数组

public int arrayPairSum(int[] nums) {

int count[] = new int[20001];

for (int x:nums) {

count[x + 10000]++;

}

int res = 0;

int index = 0;

boolean falg = true;

for(int i = 0;i = 20000;i++)

{

while(count[i] != 0)

{

nums[index++] = i - 10000;

count[i]--;

}

}

for(int i = 0;i nums.length;i = i + 2)

{

res+=nums[i];

}

return res;

}

力扣算法-561.数组拆分-数组-java 相关文章

蓝桥-【算法1-3】暴力枚举

前言 本来以为可以纯暴力解决这一类题目，没想到还混杂了大量的dp..花了几天断断续续的写完了。。 P2241 统计方形(数据加强版) import java.util.Scanner;public class Test01 { public static void main(String[] args) { Scanner uscanner/u = new Scann

2021牛客寒假算法基础集训营2 F. 牛牛与交换顺序

链接：https://ac.nowcoder.com/acm/contest/9982/F 来源：牛客网 牛牛有一个数组，数组元素是1到n的排列，即数组的值在1~n范围内，且每个数字仅出现1次。 牛牛想要将该数组变为升序排列的，他可以进行如下的操作。 首先他要确定一个长度k，k的范围在1~n之间

2021-02-03：手写代码：KMP算法。

福哥答案2021-02-03： Knuth-Morris-Pratt 字符串查找算法，简称为 KMP算法，常用于在一个文本串 S 内查找一个模式串 P 的出现位置。 这个算法由 Donald Knuth、Vaughan Pratt、James H. Morris 三人于 1977 年联合发表，故取这 3 人的姓氏命名此算法。 下面

【字符串匹配】KMP算法

目录 1.KMP的名词解释 2.KMP运行原理 3.KMP的代码 1.KMP的名词解释 KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。 具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间

C++算法代码——三连击[NOIP1998 普及组]

题目来自：https://www.luogu.com.cn/problem/P1008 题目背景 本题为提交答案题，您可以写程序或手算在本机上算出答案后，直接提交答案文本，也可提交答案生成程序。 题目描述 将1, 2, \ldots , 91,2,…,9共99个数分成33组，分别组成33个三位数，且使这33个

刷题-力扣-480

480. 滑动窗口中位数 题目链接 题目链接 来源：力扣(LeetCode) 链接：https://leetcode-cn.com/problems/sliding-window-median/ 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 题目描述 中位数是有序序列最中间的那个数。如果序

[啊哈算法]Floyd-Warshall

Input第一行四个数为n,m，n表示顶点个数，m表示边的条数。接下来m行，每一行有三个数t1、t2 和t3，表示顶点t1到顶点t2的路程是t3。请注意这些t1-t2是单向的。Output输出一个n*n的矩阵，第n行第n列表示定点n到n的距离。每一行两个数间由空格隔开Sample Input5

【算法】java语言求不定长字符串的最长子串和长度

public class interview6 { /** * 用java写一个最长子串，有一个字符串，不定长，比如abcdbafedcabcmonabcd， * 写一个方法要找出给定字符串的最长子串，最长子串是连续的不重复的字符串，返回长度(7) */ @Test public void test(){ String str="abcdbafed

?LeetCode刷题实战172：阶乘后的零

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！ 今天和大家聊的问题叫做 阶乘后的零 ，我们先来看题面： https:/

十大排序算法之选择排序(2)

2.选择排序 参考选择排序|菜鸟教程 php/** * 基础选择排序 * */function selectionSort($sortData){ $count = count($sortData); $sortCount = 0; for ($i = $count - 1; $i 0; $i--) { $max = $i; for ($j = 0; $j $i; $j++) { $sortCount++; if ($sortData