)
最大N个数和最小N个数的和
华为OD机试 - 华为OD上机考试 100分题型
华为OD机试真题目录点击查看: 华为OD机试真题题库目录｜机考题库 + 算法考点详解
题目描述
给定一个数组，编写一个函数来计算它的最大N个数与最小N个数的和。你需要对数组进行去重。
说明
- 数组中数字范围[0, 1000]
- 最大N个数与最小N个数不能有重叠，如有***重叠，输入非法***返回-1
- 输入非法返回-1
输入描述
- 第一行输入M， M标识数组大小
- 第二行输入M个数，标识数组内容
- 第三行输入N，N表达需要计算的最大、最小N个数
输出描述
输出最大N个数与最小N个数的和
用例1
输入
5 95 88 83 64 100 2输出
342说明
最大2个数[100,95],最小2个数[83,64], 输出为342。
用例2
输入
5 3 2 3 4 2 2输出
-1说明
最大2个数[4,3],最小2个数[3,2], 有重叠输出为-1。
题解
思路：逻辑分析 + 双指针
- 使用
集合对输入数组进行去重。 - 将集合转换为数组，此时判断
数组长度 >= 2 *n, 如果不成立则直接输出-1.因为会存在最大的数和最小的数重叠。 - 将数组进行升序排序，然后使用双指针计算大N个数与最小N个数的和。
- 输出结果。
c++
#include<iostream> #include<vector> #include<string> #include <utility> #include <sstream> #include<algorithm> #include<cmath> #include<set> using namespace std; int main() { int m,n; cin >> m; // 去重 set <int> uniqueNum; for (int i = 0; i < m; i++) { int tmp; cin >> tmp; uniqueNum.insert(tmp); } cin >> n; vector<int> nums(uniqueNum.begin(), uniqueNum.end()); int numLen = nums.size(); // 会存在重叠 if (numLen < 2 * n) { cout << -1; return 0; } // 升序 sort(nums.begin(), nums.end()); int left = 0, right = numLen -1; int sum = 0; // 它的最大N个数与最小N个数的和 while (n != 0) { sum += (nums[left] + nums[right]); left++; right--; n--; } cout << sum; return 0; }JAVA
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int m = sc.nextInt(); // 去重（Set 自动去重） Set<Integer> uniqueNum = new HashSet<>(); for (int i = 0; i < m; i++) { uniqueNum.add(sc.nextInt()); } int n = sc.nextInt(); // 转为数组 List<Integer> nums = new ArrayList<>(uniqueNum); int numLen = nums.size(); // 会存在重叠 if (numLen < 2 * n) { System.out.println(-1); return; } // 升序排序 Collections.sort(nums); int left = 0, right = numLen - 1; int sum = 0; // 最大 n 个数 + 最小 n 个数 while (n != 0) { sum += nums.get(left) + nums.get(right); left++; right--; n--; } System.out.println(sum); } }Python
importsysdefmain():data=list(map(int,sys.stdin.read().strip().split()))m=data[0]idx=1# 去重uniqueNum=set()for_inrange(m):uniqueNum.add(data[idx])idx+=1n=data[idx]nums=list(uniqueNum)numLen=len(nums)# 会存在重叠ifnumLen<2*n:print(-1)return# 升序nums.sort()left,right=0,numLen-1total=0# 最大 n 个数 + 最小 n 个数whilen>0:total+=nums[left]+nums[right]left+=1right-=1n-=1print(total)if__name__=="__main__":main()JavaScript
constreadline=require('readline');constrl=readline.createInterface({input:process.stdin,output:process.stdout});letinput=[];rl.on('line',line=>{input.push(...line.trim().split(/\s+/));});rl.on('close',()=>{letidx=0;constm=parseInt(input[idx++],10);// 去重constuniqueSet=newSet();for(leti=0;i<m;i++){uniqueSet.add(parseInt(input[idx++],10));}constn=parseInt(input[idx],10);constnums=Array.from(uniqueSet);constnumLen=nums.length;// 会存在重叠if(numLen<2*n){console.log(-1);return;}// 升序nums.sort((a,b)=>a-b);letleft=0,right=numLen-1;letsum=0;letcnt=n;// 最大 n 个数 + 最小 n 个数while(cnt>0){sum+=nums[left]+nums[right];left++;right--;cnt--;}console.log(sum);});Go
packagemainimport("bufio""fmt""os""sort")funcmain(){in:=bufio.NewReader(os.Stdin)varmintfmt.Fscan(in,&m)// 去重uniqueNum:=make(map[int]bool)fori:=0;i<m;i++{varxintfmt.Fscan(in,&x)uniqueNum[x]=true}varnintfmt.Fscan(in,&n)// 转为切片nums:=make([]int,0,len(uniqueNum))fork:=rangeuniqueNum{nums=append(nums,k)}numLen:=len(nums)// 会存在重叠ifnumLen<2*n{fmt.Println(-1)return}// 升序排序sort.Ints(nums)left,right:=0,numLen-1sum:=0// 最大 n 个数 + 最小 n 个数forn>0{sum+=nums[left]+nums[right]left++right--n--}fmt.Println(sum)}
