一、问题描述

题目描述

给定一个数组，编写一个函数来计算它的最大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。

题目解析

本题是一个简单的逻辑题，主要考察数组常用方法的使用，以及数组去重如何实现。

详细步骤

1. 读取输入：

   • 读取数组大小 M。
   • 读取数组内容。
   • 读取需要计算的最大、最小N个数 N。

2. 去重：

   • 使用 Set 对数组进行去重，确保每个元素唯一。

3. 排序：

   • 对去重后的数组进行排序。

4. 检查重叠：

   • 检查最大N个数和最小N个数是否有重叠。
   • 如果有重叠，返回 -1。

5. 计算和：

   • 计算最大N个数和最小N个数的和。

6. 输出结果：

   • 输出计算结果。

用例解释

用例 1

• 输入：
  • M = 5
  • 数组内容：95 88 83 64 100
  • N = 2
• 输出：
  • 342

解释：

• 去重后的数组：[95, 88, 83, 64, 100]
• 排序后的数组：[64, 83, 88, 95, 100]
• 最大2个数：[100, 95]
• 最小2个数：[64, 83]
• 计算和：100 + 95 + 64 + 83 = 342

用例 2

• 输入：
  • M = 5
  • 数组内容：3 2 3 4 2
  • N = 2
• 输出：
  • -1

解释：

• 去重后的数组：[3, 2, 4]
• 排序后的数组：[2, 3, 4]
• 最大2个数：[4, 3]
• 最小2个数：[3, 2]
• 有重叠，返回 -1

通过上述步骤，我们可以高效地求出最大N个数与最小N个数的和，确保结果符合要求。这种方法的时间复杂度主要由排序操作决定，为 O(M log M)，其中 M 是数组的长度。

二、JavaScript算法源码

以下是 JavaScript 代码 的详细中文注释和逻辑讲解：

---

JavaScript 代码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

// 创建 readline 接口实例
const rl = readline.createInterface({
  input: process.stdin,  // 输入流为标准输入
  output: process.stdout, // 输出流为标准输出
});

// 存储输入行的数组
const lines = [];

// 监听输入事件
rl.on("line", (line) => {
  lines.push(line); // 将输入行存入 lines 数组

  // 当输入行数达到 3 行时，开始处理输入
  if (lines.length === 3) {
    const m = lines[0] - 0; // 第一行输入：m，转换为数字
    const arr = lines[1].split(" ").map((ele) => Number(ele)); // 第二行输入：数组，转换为数字数组
    const n = lines[2] - 0; // 第三行输入：n，转换为数字

    // 调用算法函数并输出结果
    console.log(getResult(m, arr, n));

    // 清空 lines 数组，准备接收下一组输入
    lines.length = 0;
  }
});

// 算法函数
function getResult(m, arr, n) {
  const set = new Set(); // 使用 Set 去重

  // 遍历数组，检查每个值的合法性
  for (let val of arr) {
    if (val < 0 || val > 1000) return -1; // 如果值不在 0 到 1000 范围内，返回 -1
    set.add(val); // 将合法值添加到 Set 中
  }

  // 如果去重后的元素数量小于 2n，无法满足条件，返回 -1
  if (set.size < n * 2) {
    return -1;
  }

  // 将 Set 转换为数组并排序
  arr = [...set].sort((a, b) => a - b);

  let l = 0; // 左指针，指向数组的最小值
  let r = arr.length - 1; // 右指针，指向数组的最大值
  let ans = 0; // 存储最终结果

  // 循环 n 次，每次取最小值和最大值相加
  while (n > 0) {
    ans += arr[l] + arr[r]; // 将最小值和最大值相加
    l++; // 左指针右移
    r--; // 右指针左移
    n--; // 减少剩余需要处理的次数
  }

  return ans; // 返回最终结果
}

---

代码逻辑讲解

1. 输入处理

• 使用 readline 模块从控制台读取输入。
• 输入分为 3 行：
  1. 第一行：m，表示数组的长度（代码中未使用）。
  2. 第二行：数组 arr，包含 m 个整数。
  3. 第三行：n，表示需要处理的次数。
• 当输入行数达到 3 行时，调用算法函数 getResult 处理输入。

---

2. 算法逻辑

• 去重与合法性检查：
  • 使用 Set 对数组 arr 去重。
  • 检查每个值是否在 0 到 1000 范围内，如果超出范围，返回 -1。
• 数量检查：
  • 如果去重后的元素数量小于 2n，无法满足条件，返回 -1。
• 排序与计算：
  • 将去重后的数组排序。
  • 使用双指针法：
    • 左指针 l 指向数组的最小值。
    • 右指针 r 指向数组的最大值。
    • 每次取最小值和最大值相加，并移动指针。
    • 重复 n 次，累加结果。

---

3. 返回结果

• 返回累加的结果 ans。

---

示例验证

示例 1：

• 输入：

  5
  1 2 3 4 5
  2
  

• 处理过程：
  1. 去重后的数组：[1, 2, 3, 4, 5]。
  2. 排序后的数组：[1, 2, 3, 4, 5]。
  3. 双指针计算：
     • 第一次：1 + 5 = 6。
     • 第二次：2 + 4 = 6。
  4. 结果：6 + 6 = 12。
• 输出：12。

示例 2：

• 输入：

  4
  10 20 30 40
  1
  

• 处理过程：
  1. 去重后的数组：[10, 20, 30, 40]。
  2. 排序后的数组：[10, 20, 30, 40]。
  3. 双指针计算：
     • 第一次：10 + 40 = 50。
  4. 结果：50。
• 输出：50。

示例 3：

• 输入：

  3
  1 1 2
  2
  

• 处理过程：
  1. 去重后的数组：[1, 2]。
  2. 数量检查：2 < 2 * 2，不满足条件。
  3. 结果：-1。
• 输出：-1。

---

总结

• 功能：从数组中选取 n 对最小值和最大值，计算它们的和。
• 核心逻辑：
  1. 去重并检查值的合法性。
  2. 检查去重后的元素数量是否满足条件。
  3. 使用双指针法计算最小值和最大值的和。
• 适用场景：需要从数组中选取特定数量的最小值和最大值进行计算的场景。
• 注意事项：
  • 输入数组中的值必须在 0 到 1000 范围内。
  • 去重后的元素数量必须至少为 2n，否则无法满足条件。

如果有其他问题，欢迎随时提问！

三、Java算法源码

以下是 Java 代码 的详细中文注释和逻辑讲解：

---

Java 代码

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in); // 创建 Scanner 对象，用于读取输入

    int m = sc.nextInt(); // 读取数组的长度 m

    int[] arr = new int[m]; // 创建长度为 m 的数组
    for (int i = 0; i < m; i++) {
      arr[i] = sc.nextInt(); // 读取数组的每个元素
    }

    int n = sc.nextInt(); // 读取需要处理的次数 n

    System.out.println(getResult(m, arr, n)); // 调用算法函数并输出结果
  }

  // 算法函数
  public static int getResult(int m, int[] arr, int n) {
    HashSet<Integer> set = new HashSet<>(); // 使用 HashSet 去重

    // 遍历数组，检查每个值的合法性
    for (int val : arr) {
      if (val < 0 || val > 1000) return -1; // 如果值不在 0 到 1000 范围内，返回 -1
      set.add(val); // 将合法值添加到 HashSet 中
    }

    // 如果去重后的元素数量小于 2n，无法满足条件，返回 -1
    if (set.size() < n * 2) return -1;

    // 将 HashSet 转换为数组并排序
    Integer[] distinct_arr = set.toArray(new Integer[0]);
    Arrays.sort(distinct_arr, (a, b) -> a - b);

    int l = 0; // 左指针，指向数组的最小值
    int r = distinct_arr.length - 1; // 右指针，指向数组的最大值
    int ans = 0; // 存储最终结果

    // 循环 n 次，每次取最小值和最大值相加
    while (n > 0) {
      ans += distinct_arr[l] + distinct_arr[r]; // 将最小值和最大值相加
      l++; // 左指针右移
      r--; // 右指针左移
      n--; // 减少剩余需要处理的次数
    }

    return ans; // 返回最终结果
  }
}

---

代码逻辑讲解

1. 输入处理

• 使用 Scanner 从控制台读取输入。
• 输入分为 3 部分：
  1. 第一行：m，表示数组的长度。
  2. 第二行：数组 arr，包含 m 个整数。
  3. 第三行：n，表示需要处理的次数。

---

2. 算法逻辑

• 去重与合法性检查：
  • 使用 HashSet 对数组 arr 去重。
  • 检查每个值是否在 0 到 1000 范围内，如果超出范围，返回 -1。
• 数量检查：
  • 如果去重后的元素数量小于 2n，无法满足条件，返回 -1。
• 排序与计算：
  • 将去重后的数组转换为 Integer 数组并排序。
  • 使用双指针法：
    • 左指针 l 指向数组的最小值。
    • 右指针 r 指向数组的最大值。
    • 每次取最小值和最大值相加，并移动指针。
    • 重复 n 次，累加结果。

---

3. 返回结果

• 返回累加的结果 ans。

---

示例验证

示例 1：

• 输入：

  5
  1 2 3 4 5
  2
  

• 处理过程：
  1. 去重后的数组：[1, 2, 3, 4, 5]。
  2. 排序后的数组：[1, 2, 3, 4, 5]。
  3. 双指针计算：
     • 第一次：1 + 5 = 6。
     • 第二次：2 + 4 = 6。
  4. 结果：6 + 6 = 12。
• 输出：12。

示例 2：

• 输入：

  4
  10 20 30 40
  1
  

• 处理过程：
  1. 去重后的数组：[10, 20, 30, 40]。
  2. 排序后的数组：[10, 20, 30, 40]。
  3. 双指针计算：
     • 第一次：10 + 40 = 50。
  4. 结果：50。
• 输出：50。

示例 3：

• 输入：

  3
  1 1 2
  2
  

• 处理过程：
  1. 去重后的数组：[1, 2]。
  2. 数量检查：2 < 2 * 2，不满足条件。
  3. 结果：-1。
• 输出：-1。

---

总结

• 功能：从数组中选取 n 对最小值和最大值，计算它们的和。
• 核心逻辑：
  1. 去重并检查值的合法性。
  2. 检查去重后的元素数量是否满足条件。
  3. 使用双指针法计算最小值和最大值的和。
• 适用场景：需要从数组中选取特定数量的最小值和最大值进行计算的场景。
• 注意事项：
  • 输入数组中的值必须在 0 到 1000 范围内。
  • 去重后的元素数量必须至少为 2n，否则无法满足条件。

如果有其他问题，欢迎随时提问！

四、Python算法源码

以下是 Python 代码 的详细中文注释和逻辑讲解：

---

Python 代码

# 输入获取
m = int(input())  # 读取数组的长度 m
arr = list(map(int, input().split()))  # 读取数组的每个元素，并转换为整数列表
n = int(input())  # 读取需要处理的次数 n


# 算法入口
def getResult(m, arr, n):
    # 对数组进行去重
    arr = list(set(arr))

    # 最大N个数与最小N个数不能有重叠，如有重叠，输入非法返回-1
    if len(arr) < n * 2:
        return -1

    # 对数组进行排序
    arr.sort()

    # 数组中数字范围[0, 1000]，如果超出范围，返回-1
    if arr[0] < 0 or arr[-1] > 1000:
        return -1

    # 计算最大N个数与最小N个数的和
    return sum(arr[:n]) + sum(arr[-n:])


# 算法调用
print(getResult(m, arr, n))  # 调用算法函数并输出结果

---

代码逻辑讲解

1. 输入处理

• 使用 input() 函数从控制台读取输入。
• 输入分为 3 部分：
  1. 第一行：m，表示数组的长度。
  2. 第二行：数组 arr，包含 m 个整数。
  3. 第三行：n，表示需要处理的次数。

---

2. 算法逻辑

• 去重：
  • 使用 set 对数组 arr 去重，并转换为列表。
• 数量检查：
  • 如果去重后的元素数量小于 2n，无法满足条件，返回 -1。
• 排序：
  • 对去重后的数组进行升序排序。
• 合法性检查：
  • 检查数组中的最小值是否小于 0 或最大值是否大于 1000，如果超出范围，返回 -1。
• 计算和：
  • 取数组的前 n 个最小值和后 n 个最大值，计算它们的和。

---

3. 返回结果

• 返回最小值和最大值的和。

---

示例验证

示例 1：

• 输入：

  5
  1 2 3 4 5
  2
  

• 处理过程：
  1. 去重后的数组：[1, 2, 3, 4, 5]。
  2. 排序后的数组：[1, 2, 3, 4, 5]。
  3. 计算：
     • 最小值：1 + 2 = 3。
     • 最大值：4 + 5 = 9。
  4. 结果：3 + 9 = 12。
• 输出：12。

示例 2：

• 输入：

  4
  10 20 30 40
  1
  

• 处理过程：
  1. 去重后的数组：[10, 20, 30, 40]。
  2. 排序后的数组：[10, 20, 30, 40]。
  3. 计算：
     • 最小值：10。
     • 最大值：40。
  4. 结果：10 + 40 = 50。
• 输出：50。

示例 3：

• 输入：

  3
  1 1 2
  2
  

• 处理过程：
  1. 去重后的数组：[1, 2]。
  2. 数量检查：2 < 2 * 2，不满足条件。
  3. 结果：-1。
• 输出：-1。

---

总结

• 功能：从数组中选取 n 个最小值和 n 个最大值，计算它们的和。
• 核心逻辑：
  1. 去重并检查值的合法性。
  2. 检查去重后的元素数量是否满足条件。
  3. 使用排序和切片计算最小值和最大值的和。
• 适用场景：需要从数组中选取特定数量的最小值和最大值进行计算的场景。
• 注意事项：
  • 输入数组中的值必须在 0 到 1000 范围内。
  • 去重后的元素数量必须至少为 2n，否则无法满足条件。

如果有其他问题，欢迎随时提问！

五、C/C++算法源码：

以下是 C++ 代码 和 C 语言代码 的详细中文注释和逻辑讲解：

---

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>

using namespace std;

// 算法入口
int getResult(int m, vector<int>& arr, int n) {
    // 使用 unordered_set 对数组去重
    unordered_set<int> uniqueSet(arr.begin(), arr.end());
    vector<int> uniqueArr(uniqueSet.begin(), uniqueSet.end());

    // 最大N个数与最小N个数不能有重叠，如有重叠，输入非法返回-1
    if (uniqueArr.size() < n * 2) {
        return -1;
    }

    // 对数组进行排序
    sort(uniqueArr.begin(), uniqueArr.end());

    // 数组中数字范围[0, 1000]，如果超出范围，返回-1
    if (uniqueArr[0] < 0 || uniqueArr.back() > 1000) {
        return -1;
    }

    // 计算最大N个数与最小N个数的和
    int sumMin = 0, sumMax = 0;
    for (int i = 0; i < n; i++) {
        sumMin += uniqueArr[i];            // 前n个最小值
        sumMax += uniqueArr[uniqueArr.size() - 1 - i]; // 后n个最大值
    }

    return sumMin + sumMax;
}

int main() {
    // 输入获取
    int m, n;
    cin >> m;
    vector<int> arr(m);
    for (int i = 0; i < m; i++) {
        cin >> arr[i];
    }
    cin >> n;

    // 算法调用
    cout << getResult(m, arr, n) << endl;

    return 0;
}

---

C 语言代码

#include <stdio.h>
#include <stdlib.h>

// 比较函数，用于排序
int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

// 算法入口
int getResult(int m, int arr[], int n) {
    // 使用数组去重
    int uniqueArr[1000]; // 假设数组最大长度为1000
    int uniqueCount = 0;

    for (int i = 0; i < m; i++) {
        int isDuplicate = 0;
        for (int j = 0; j < uniqueCount; j++) {
            if (arr[i] == uniqueArr[j]) {
                isDuplicate = 1;
                break;
            }
        }
        if (!isDuplicate) {
            uniqueArr[uniqueCount++] = arr[i];
        }
    }

    // 最大N个数与最小N个数不能有重叠，如有重叠，输入非法返回-1
    if (uniqueCount < n * 2) {
        return -1;
    }

    // 对数组进行排序
    qsort(uniqueArr, uniqueCount, sizeof(int), compare);

    // 数组中数字范围[0, 1000]，如果超出范围，返回-1
    if (uniqueArr[0] < 0 || uniqueArr[uniqueCount - 1] > 1000) {
        return -1;
    }

    // 计算最大N个数与最小N个数的和
    int sumMin = 0, sumMax = 0;
    for (int i = 0; i < n; i++) {
        sumMin += uniqueArr[i];            // 前n个最小值
        sumMax += uniqueArr[uniqueCount - 1 - i]; // 后n个最大值
    }

    return sumMin + sumMax;
}

int main() {
    // 输入获取
    int m, n;
    scanf("%d", &m);
    int arr[m];
    for (int i = 0; i < m; i++) {
        scanf("%d", &arr[i]);
    }
    scanf("%d", &n);

    // 算法调用
    printf("%d\n", getResult(m, arr, n));

    return 0;
}

---

代码逻辑讲解

1. 输入处理

• C++：
  • 使用 cin 从控制台读取输入。
  • 输入分为 3 部分：
    1. 第一行：m，表示数组的长度。
    2. 第二行：数组 arr，包含 m 个整数。
    3. 第三行：n，表示需要处理的次数。
• C 语言：
  • 使用 scanf 从控制台读取输入。
  • 输入分为 3 部分：
    1. 第一行：m，表示数组的长度。
    2. 第二行：数组 arr，包含 m 个整数。
    3. 第三行：n，表示需要处理的次数。

---

2. 算法逻辑

• 去重：
  • C++：使用 unordered_set 对数组去重。
  • C 语言：手动遍历数组去重。
• 数量检查：
  • 如果去重后的元素数量小于 2n，无法满足条件，返回 -1。
• 排序：
  • C++：使用 sort 函数对数组排序。
  • C 语言：使用 qsort 函数对数组排序。
• 合法性检查：
  • 检查数组中的最小值是否小于 0 或最大值是否大于 1000，如果超出范围，返回 -1。
• 计算和：
  • 取数组的前 n 个最小值和后 n 个最大值，计算它们的和。

---

3. 返回结果

• 返回最小值和最大值的和。

---

示例验证

示例 1：

• 输入：

  5
  1 2 3 4 5
  2
  

• 处理过程：
  1. 去重后的数组：[1, 2, 3, 4, 5]。
  2. 排序后的数组：[1, 2, 3, 4, 5]。
  3. 计算：
     • 最小值：1 + 2 = 3。
     • 最大值：4 + 5 = 9。
  4. 结果：3 + 9 = 12。
• 输出：12。

示例 2：

• 输入：

  4
  10 20 30 40
  1
  

• 处理过程：
  1. 去重后的数组：[10, 20, 30, 40]。
  2. 排序后的数组：[10, 20, 30, 40]。
  3. 计算：
     • 最小值：10。
     • 最大值：40。
  4. 结果：10 + 40 = 50。
• 输出：50。

示例 3：

• 输入：

  3
  1 1 2
  2
  

• 处理过程：
  1. 去重后的数组：[1, 2]。
  2. 数量检查：2 < 2 * 2，不满足条件。
  3. 结果：-1。
• 输出：-1。

---

总结

• 功能：从数组中选取 n 个最小值和 n 个最大值，计算它们的和。
• 核心逻辑：
  1. 去重并检查值的合法性。
  2. 检查去重后的元素数量是否满足条件。
  3. 使用排序和切片计算最小值和最大值的和。
• 适用场景：需要从数组中选取特定数量的最小值和最大值进行计算的场景。
• 注意事项：
  • 输入数组中的值必须在 0 到 1000 范围内。
  • 去重后的元素数量必须至少为 2n，否则无法满足条件。

如果有其他问题，欢迎随时提问！