LeetCode算法题-Array Partition I(Java实现)

来源:http://www.chinese-glasses.com 作者:Web前端 人气:174 发布时间:2020-04-07
摘要:时间: 2019-10-18阅读: 70标签: 算法 这是悦乐书的第 262 次更新,第 275 篇原创 计数排序是一个非基于比较的[排序算法],该算法于1954年由 Harold H.Seward提出。它的优势在于在对一定范围内的

时间: 2019-10-18阅读: 70标签: 算法

这是悦乐书的第262次更新,第275篇原创

计数排序是一个非基于比较的[排序算法],该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时,它的复杂度为Ο(n+k)(其中k是整数的范围),快于任何比较排序算法。

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第129题。给定一个2n个整数的数组,你的任务是将这些整数分组为n对整数,比如说,,...,,找出每对中最小值,然后相加,使得其和最大。例如:

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

输出:4

说明:n为2,对的最大总和为4 = min+ min。

注意:

  • n是正整数,其范围为[1,10000]。

  • 数组中的所有整数都在[-10000,10000]的范围内。

本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。

[1]当然这是一种牺牲空间换取时间的做法,而且当O(k)O(n*log(n))的时候其效率反而不如基于比较的排序(基于比较的排序的时间复杂度在理论上的下限是O(n*log(n)), 如归并排序,堆排序)

02 第一种解法

题目要求我们计算每两个数中最小数之和的最大值。以题目中的数组为例,{1,4,2,3},四个数组成任意两对组合:

{,},最小值之和为1+2=3

{,},最小值之和为1+3=4

{,},最小值之和为1+2=3

可以发现只有{,}这一对的结果是最大的,从另外一个角度来讲,要想最后的和最大,那么每对数之间的差就要越小,因为两数之间差越大,大的数就被pass掉了,无法在后面的配对中起作用。所以,要想每对数之间的差越小,可以通过排序来完成,取相邻的数作为一对,计算最小值之和,也就变成求奇数位元素值之和了。

此解法的时间复杂度是O,空间复杂度是O。

public int arrayPairSum(int[] nums) { Arrays.sort; int sum = 0; for (int i=0; i<nums.length; i += 2) { sum += nums[i]; } return sum;}

解释

03 第二种解法

对于第一种解法,我们可以使用记数排序法,将时间复杂度降到O,但是要牺牲一定的空间。

记数排序法,在这里大致讲下,不展开。对于有限个数的整数数组,如果知道每个元素前面有多少位,我们可以很快速的做出排序。

比如{1,7,5,2,8,2,7},使用一个长度为9的新数组来记数,{0,1,2,0,0,1,0,2,1},其中不为0的数分别表示1个1,2个2,1个5,2个7,1个8,然后按照依次出现的次数打印出来(跳过元素值为0的索引)就变成{1,2,2,5,7,7,8},也就实现了排序。

这第二种解法就是利用记数排序来替换原来的比较排序,此解法的时间复杂度是O,最坏的情况是O,其中k是整数的范围,空间复杂度是O。

public int arrayPairSum2(int[] nums) { // 原数组大小为20000,我们比它多一位即可 int[] temp = new int[20001]; // 原数组元素的取值范围是[-10000,10000],以旧数组的元素值作为索引,不能存在负值,所以加上10000 // 统计每个元素出现的次数 for (int i=0; i<nums.length; i++) { temp[nums[i]+10000]++; } // 新建一个和原数组大小一致的数组,来承接排序后的新元素值 int[] temp2 = new int[nums.length]; // 新数组temp2的索引值 int index = 0; for (int i=0; i<temp.length; i++) { // 只有temp的元素不为0,说明遇到了nums的元素 if (temp[i] != 0) { // 表明出现了temp[i]次的nums中的元素, for (int j=0; j<temp[i]; j++) { // 上面对nums的元素加过10000,此处要还原 temp2[index++] = i-10000; } } } int sum = 0; // 排完序后新的数组temp2,依旧取第奇数位元素相加求和 for (int i=0; i<temp2.length; i += 2) { sum += temp2[i]; } return sum;}

以上是百度百科(最近无法科学上网..)关于记数排序的描述。核心点如下:

04 第三种解法

对于第二种解法,我们还可以优化下,变得更加简单点。在记数完成后,直接对新数组中的数据进行处理。

因为我们只要排在第奇数位的元素,所以引用一个布尔类型的变量odd,当temp[i]大于0的时候,表示遇到了nums中的元素,拿到nums的元素依旧是新数组的索引i减去10000,加完一次后odd变量需要变成false,在第3次进来的时候,再加上当前元素,如果当前元素出现了多次的话。

public int arrayPairSum3(int[] nums) { int[] temp = new int[20001]; for (int i=0; i<nums.length; i++) { temp[nums[i]+10000]++; } int sum = 0; boolean odd = true; for (int i=0; i<temp.length; i++) { while (temp[i] > 0) { if  { sum += i-10000; } odd = !odd; temp[i]--; } } return sum;}

是一种非比较的排序需要一个累计数组来记录原数组的信息累计数组的索引就是原数组的值累计数组的值就是原数组某元素重复出现的次数

05 小结

算法专题目前已日更超过三个月,算法题文章129+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

10bet,非比较排序就是说不比较数组中元素的大小关系。而是通过记录索引的方式巧妙的将原数组进行排序。这样说比较绕,接下来就分步骤说明:

比如说,现在有一个这样的数组:

constarr = [2,1,2,2,3,8,5,5,9]

如果要对其进行记数排序的话,大概需要这几步:

  1. 定义累计数组 其中length是原数组的最大值+1

    // 原数组最大值 const max = Math.max(...arr); // 定义一个累计数组 数组长度是最大值+1 元素都是0 // 累计数组第一位的空位0 所以长度要+1 const _arr = new Array(max + 1).fill(0);

  2. 将原数组中的值转换为累计数组的索引

将原数组中的值转换为累计数组的索引,遇到重复的元素,就在累计数组中进行累加。比如: 在原数组中的元素1出现了1次,那么在累计数组中索引为1的元素的值为1。在原数组中的元素2重复出现了3次,那么在累计数组中索引为2的元素的值为3。在原数组中的元素5重复出现了2次,那么在累计数组中索引为5的元素的值为2。其他以此类推。此时累计数组就变成了:(其实通过此步,就已经将数组排好序了,因为值越大 索引越靠后)

_arr = [0,1,3,1,0,2,0,0,1,1]

本文由10bet发布于Web前端,转载请注明出处:LeetCode算法题-Array Partition I(Java实现)

关键词:

上一篇:没有了

下一篇:做技术,35岁,你慌了吗?

最火资讯