2740. 找出分区值

🟠   🔖  数组 排序  🔗 力扣 LeetCode

题目

You are given a positive integer array nums.

Partition nums into two arrays, nums1 and nums2, such that:

• Each element of the array nums belongs to either the array nums1 or the array nums2.
• Both arrays are non-empty.
• The value of the partition is minimized.

The value of the partition is |max(nums1) - min(nums2)|.

Here, max(nums1) denotes the maximum element of the array nums1, and min(nums2) denotes the minimum element of the array nums2.

Return the integer denoting the value of such partition.

Example 1:

Input: nums = [1,3,2,4]

Output: 1

Explanation: We can partition the array nums into nums1 = [1,2] and nums2 = [3,4].

• The maximum element of the array nums1 is equal to 2.
• The minimum element of the array nums2 is equal to 3.

The value of the partition is |2 - 3| = 1.

It can be proven that 1 is the minimum value out of all partitions.

Example 2:

Input: nums = [100,1,10]

Output: 9

Explanation: We can partition the array nums into nums1 = [10] and nums2 = [100,1].

• The maximum element of the array nums1 is equal to 10.
• The minimum element of the array nums2 is equal to 1.

The value of the partition is |10 - 1| = 9.

It can be proven that 9 is the minimum value out of all partitions.

Constraints:

• 2 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9

题目大意

给你一个 正 整数数组 nums 。

将 nums 分成两个数组：nums1 和 nums2 ，并满足下述条件：

• 数组 nums 中的每个元素都属于数组 nums1 或数组 nums2 。
• 两个数组都 非空 。
• 分区值 最小 。

分区值的计算方法是 |max(nums1) - min(nums2)| 。

其中，max(nums1) 表示数组 nums1 中的最大元素，min(nums2) 表示数组 nums2 中的最小元素。

返回表示分区值的整数。

示例 1：

输入： nums = [1,3,2,4]

输出： 1

解释： 可以将数组 nums 分成 nums1 = [1,2] 和 nums2 = [3,4] 。

• 数组 nums1 的最大值等于 2 。
• 数组 nums2 的最小值等于 3 。

分区值等于 |2 - 3| = 1 。

可以证明 1 是所有分区方案的最小值。

示例 2：

输入： nums = [100,1,10]

输出： 9

解释： 可以将数组 nums 分成 nums1 = [10] 和 nums2 = [100,1] 。

• 数组 nums1 的最大值等于 10 。
• 数组 nums2 的最小值等于 1 。

分区值等于 |10 - 1| = 9 。

可以证明 9 是所有分区方案的最小值。

提示：

• 2 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9

解题思路

1. 排序：由于题目要求最小分区值，因此可以先对数组进行排序，让元素按递增值排序，这有助于最小化相邻元素之间的绝对差异。

2. 寻找最小分区值：遍历已排序的元素，依次将相邻元素相减，计算每个分区处的差异并返回最小的差异。

复杂度分析

• 时间复杂度：O(n logn)，其中 n 是数组的长度，排序的时间复杂度为 O(n logn)，遍历数组计算分区值的时间复杂度为 O(n)，所以总的时间复杂度为 O(n logn)。
• 空间复杂度：O(1)，只使用了常数个过程变量。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var findValueOfPartition = function (nums) {
	let res = Infinity;
	nums.sort((a, b) => a - b);

	for (let i = 1; i < nums.length; i++) {
		res = Math.min(res, nums[i] - nums[i - 1]);
	}
	return res;
};