每日力扣算法题(简单篇)
561.数组拆分
原题:
给定长度为 2n
的整数数组 nums
,你的任务是将这些数分成 n
对, 例如 (a1, b1), (a2, b2), ..., (an, bn)
,使得从 1
到 n
的 min(ai, bi)
总和最大。
返回该 最大总和 。
解题思路:
我们可以发现取一个数对如果这两个数字之间的差值越小,那么我们可以得到总和也就越大,那我们就可以很自然的想到,如果有一个数据是[3,2,1,4]我们将其排序得到[1,2,3,4]那么这个时候我们如果将其第0和第1号元素看作一个数对,第2和第3看作一个数对,我们就可以得到每个数对取最小的结果的最大和
知识储备:
qsort函数,函数原型:qsort(指针,元素个数,每个元素所占字节大小,指向比较函数的指针),效果:将数组中的数据从小到大排序
都看到这里了,点个赞吧,可以的话点个关注吧
源代码:
int cmp(const void* a,const void* b)
{int numa=*(int*)a;int numb=*(int*)b;return numa>numb?1:-1;
}
int arrayPairSum(int* nums, int numsSize) {qsort(nums,numsSize,sizeof(int),cmp);int sum=0;for(int i=0;i<numsSize;i+=2){sum+=nums[i];}return sum;
}