首页 > 试题广场 >

两两配对差值最小

[编程题]两两配对差值最小

给定一个长度为偶数的数组arr，将该数组中的数字两两配对并求和，在这些和中选出最大和最小值，请问该如何两两配对，才能让最大值和最小值的差值最小？

一共2行输入。
第一行为一个整数n，2<=n<=10000, 第二行为n个数，，组成arr数组，0<=arr[i]<=100。

输出最小的差值。

示例1

输入

4
2 6 4 3

示例2

6
11 4 3 5 7 1

算法知识视频讲解

残魂：：残剑

发表于 2021-09-21 12:47:15

#include <iostream> #include <cmath> #include <algorithm> using namespace std; const int N=1000035; int a[N]; int main() { in 展开全文

牛客题解官

发表于 2020-06-05 18:49:23

题解：题目难度：二星考察点：贪心，排序，哈希解法一：贪心+排序将一个数列中的所有数两两配对并求和，在这些和中选出最大和最小值，使得二者差距最小。很显然就是要让所有的配对的和的大小尽量相等，试想一下，如果让大的和大的配对，小的和小的配对，那么最大值和最小值的差距将会进一步拉大，因此一种可行的展开全文

C++工程师 golang工程师 iOS工程师数组安卓工程师运维工程师前端工程师算法工程师测试工程师 PHP工程师排序贪心 2019 拼多多 Java工程师

上传者：小小

难度：

42条回答 59收藏 13015浏览

查看代码

扫一扫，把题目装进口袋