目录

题目

思路

Code

题目

给定 n 个整数，需要将它们任意分成两组，且两组都不能为空。

对于一组数，它的极差定义为该组中的最大值减去最小值。

设两组分别为第 1 组和第 2 组，则它们的极差分别为：

第 1 组极差 = 第 1 组最大值 - 第 1 组最小值

第 2 组极差 = 第 2 组最大值 - 第 2 组最小值

目标是最小化两个极差之和：

(max1 - min1) + (max2 - min2)

请输出这个最小值。

输入描述

输入一个整数数组 nums，表示待分组的整数集合。

输出描述

输出一个整数，表示把数组分成两个非空组后，两组极差之和的最小值。

样例 1

输入：

[1,1,9,9,1]

输出：

0

说明：可以分为 [1,1,1] 和 [9,9]，两组极差分别为 1 - 1 = 0、9 - 9 = 0，极差和为 0。

样例 2

输入：

[1,2,3,4]

输出：

2

说明：排序后切分为 [1,2] 与 [3,4]，极差和为 (2 - 1) + (4 - 3) = 2。

思路

逻辑模拟题

先把数组排序。排序后，如果某个分组中同时拿了很小和很大的数，中间的数放到另一组通常不会让总极差更优，因此最优方案可以看成在有序数组中切一刀，左边一组、右边一组。枚举所有切分位置，计算左组极差加右组极差，取最小值。

Code

import ast

nums = ast.literal_eval(input().strip())
# 排序后只需要枚举一刀切分点，左右两段分别作为两组。
nums.sort()
# 遍历所有切分点，不断更新最小代价。
ans = 10 ** 18

# 每个切分点的代价等于左段极差加右段极差。
for i in range(len(nums) - 1):
    # 排序后切成 [0..i] 和 [i+1..n-1] 两组。
    cur = (nums[i] - nums[0]) + (nums[-1] - nums[i + 1])
    ans = min(ans, cur)
# 输出两组极差和的最小值。
print(ans)

JS

const fs = require("fs");

// 从数组字符串中提取所有整数，排序后再处理分组。
const nums = (fs.readFileSync(0, "utf8").match(/-?\d+/g) || []).map(Number);
// 排序后只需要枚举一刀切分点，左右两段分别作为两组。
nums.sort((a, b) => a - b);

// 遍历所有切分点，不断更新最小代价。
let ans = Infinity;
// 每个切分点的代价等于左段极差加右段极差。
for (let i = 0; i + 1 < nums.length; i++) {
  // 排序后切一刀，分别计算两段极差。
  const cur = (nums[i] - nums[0]) + (nums[nums.length - 1] - nums[i + 1]);
  ans = Math.min(ans, cur);
}
// 输出两组极差和的最小值。
console.log(ans);

【华为od机试真题Python+JS+Java+Go合集】【超值优惠】：Py/JS/Java/Go合集

【华为od机试真题Python】：Python真题题库

【华为od机试真题JavaScript】：JavaScript真题题库

【华为od机试真题Java&Go】：Java&Go真题题库

【华为od机试真题C++】：C++真题题库

【华为od机试真题C语言】：C语言真题题库

【华为od面试手撕代码题库】：面试手撕代码题库

【华为od机试面试交流群】【文章底部有二维码链接，可扫码加交流群】

华为OD机试:二本院校有机会吗?
有机会,但不大,大神除外!机考分数越高越好,所以需要提前刷题。机考通过后,如果没有收到面试邀请,也不要着急,非目标院校面试邀请发的时间比较晚。非目标院校今年有点难,机试至少要考到350分,所以需要疯狂刷题,华为OD机考是有题库的,最好在考前完所有题库题目。华为OD机试:跨专业可以参加华为OD可以,但是如果你的本科院校比较差,上岸概率不大。华为OD机试:华为OD简历被锁定机试通过,性格测试也通过,但是没人联系面试,发现简历被锁定。此时需要主动去联系HR。让他帮助你查询原因。