华为OD机试 - 最大N个数与最小N个数的和 - 数据结构Set与TreeSet（Java 2023 B卷 100分）

在这里插入图片描述

一、题目描述

给定一个数组，编写一个函数来计算它的最大N个数与最小N个数的和，需要对数组进行去重。

说明：

数组中数字范围[0, 1000]
最大N个数与最小N个数不能有重叠，如有重叠，输入非法返回-1
输入非法返回-1

二、输入描述

第一行输入M， M表示数组大小
第二行输入M个数，表示数组内容
第三行输入N，N表示需要计算的最大、最小N个数

三、输出描述

输出最大N个数与最小N个数的和。

四、解题思路

本题的关键点是通过数据结构Set进行去重，通过TreeSet进行升序排序。

第一行输入数组大小M；
第二行输入M个数字，空格隔开；
第三行输入需要计算的最大、最小N个数；
需要对数组进行去重，因此用Set将第二行的M个数字加入Set；
将Set进行升序排序，方便计算最大的和最小的N个数之和；
遍历升序的treeSet；
取最小的N个数之和；
取最大的N个数之和；
再将两者相加，得出结果。

例如：

7
47 17 26 9 18 47 52
3

在这里插入图片描述

五、Java算法源码

package com.guor.od;

import java.util.*;

public class OdTest01 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 数组大小
        int M = Integer.parseInt(sc.nextLine());
        // 需要对数组进行去重，因此用Set
        Set<Integer> set = new HashSet<>();
        // 输入M个数，表示数组内容
        for (String s : sc.nextLine().split(" ")) {
            set.add(Integer.valueOf(s));
        }
        // 需要计算的最大、最小N个数
        int N = Integer.parseInt(sc.nextLine());

        // 将Set进行升序排序，方便计算最大的和最小的N个数之和
        Set<Integer> treeSet = new TreeSet<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                if (o1 > o2) {
                    return 1;
                } else if (o1 < o2) {
                    return -1;
                } else {
                    return 0;
                }
            }
        });
        treeSet.addAll(set);

        // 最小N个数之和
        int sumSmall = 0;
        // 最大N个数之和
        int sumBig = 0;
        int i = 0;
        for (Integer num : treeSet) {
            if (i < N) {
                System.out.println("最小N个数：" + num);
                sumSmall += num;
            }
            if (i >= treeSet.size() - N) {
                System.out.println("最大N个数：" + num);
                sumBig += num;
            }
            i++;
        }

        System.out.println("最大N个数与最小N个数的和:"+(sumSmall + sumBig));
    }
}