LeetCode 题解工作台
找出分区值
给你一个 正 整数数组 nums 。 将 nums 分成两个数组： nums1 和 nums2 ，并满足下述条件： 数组 nums 中的每个元素都属于数组 nums1 或数组 nums2 。 两个数组都 非空 。 分区值 最小 。 分区值的计算方法是 |max(nums1) - min(nums2)…
2
题型
6
代码语言
3
相关题
当前训练重点
中等 · 数组·排序
答案摘要
题目要求分区值最小，那么我们可以将数组排序，然后取相邻两个数的差值的最小值即可。 时间复杂度 $O(n \times \log n)$，空间复杂度 $O(\log n)$。其中 是数组的长度。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·排序 题型思路
题目描述
给你一个 正 整数数组 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 <= 1051 <= nums[i] <= 109
解题思路
方法一：排序
题目要求分区值最小，那么我们可以将数组排序，然后取相邻两个数的差值的最小值即可。
时间复杂度 ，空间复杂度 。其中 是数组的长度。
class Solution:
def findValueOfPartition(self, nums: List[int]) -> int:
nums.sort()
return min(b - a for a, b in pairwise(nums))
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Ask if sorting simplifies the partition calculation.
- question_mark
Check understanding of Array plus Sorting pattern.
- question_mark
Probe knowledge of minimizing difference between subarray extremes.
常见陷阱
外企场景- error
Not sorting before checking partitions leads to incorrect minimum values.
- error
Attempting all subset splits results in time limit exceeded for large arrays.
- error
Forgetting that the array must be split into two non-empty subarrays.
进阶变体
外企场景- arrow_right_alt
Find the partition value in a descending array without sorting first.
- arrow_right_alt
Compute maximum partition value instead of minimum.
- arrow_right_alt
Handle arrays with duplicate elements while minimizing partition value.