找出分区值

标签: 数组 排序

难度: Medium

给你一个 正 整数数组 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 <= 105
  • 1 <= nums[i] <= 109

Submission

运行时间: 97 ms

内存: 27.4 MB

class Solution:
    def findValueOfPartition(self, nums: List[int]) -> int:
        nums.sort()
        a = nums[1]-nums[0]
        for i in range(1,len(nums)):
            if nums[i]-nums[i-1]<a:
                a = nums[i]-nums[i-1]
        return a

Explain

该题解通过首先对数组进行排序，然后计算相邻元素之间的最小差值来实现。因为在一个排序的数组中，两个子数组最优分割点就在最小的差值的两个元素之间，即这两个元素分别是两个子数组中的边界元素。这样可以保证计算出来的 |max(nums1) - min(nums2)| 最小。

时间复杂度: O(n log n)

空间复杂度: O(1)

class Solution:
    def findValueOfPartition(self, nums: List[int]) -> int:
        nums.sort()  # 对数组进行排序
        a = nums[1]-nums[0]  # 初始化最小差值为第一个和第二个元素的差
        for i in range(1,len(nums)):
            if nums[i]-nums[i-1]<a:
                a = nums[i]-nums[i-1]  # 找到相邻元素之间的最小差值
        return a  # 返回这个最小差值作为最小的分区值

Explore

在排序后的数组中，相邻元素之间的差值是最小的相对差值，因为它们在值上是最接近的。当数组被分为两个子数组时，最小的分区值应该是两个子数组之间差值的最小可能值，这通常发生在两个最接近的数之间，即它们在排序数组中是相邻的。因此，计算排序数组中相邻元素的最小差值可以有效地找到最小的分区值，确保 |max(nums1) - min(nums2)| 最小化。

初始化最小差值 `a` 为数组中第一个元素和第二个元素的差是因为这是在排序后数组中第一对相邻元素，它提供了一个合理的初始参考值。从这对元素开始，算法可以通过遍历数组来检查是否有更小的相邻差值存在。如果使用更大的值初始化，可能需要额外的条件检查来确定是否有更小的差值；如果使用其他非相邻元素的差，可能错过最小差值。

当数组 `nums` 只有两个元素时，这种方法仍然有效。在这种情况下，数组排序后（如果它们不是已排序的），唯一的相邻元素就是这两个元素本身。因此，计算这两个元素之间的差值直接给出了最小的分区值。这是边界条件下的预期结果，符合算法设计的目的。

如果已知输入数组 `nums` 是排序状态的，那么没有必要再次进行排序。可以直接跳到计算相邻元素的差值的步骤。这样可以省略排序的时间复杂度，使算法更加高效。然而，除非明确指出数组已排序，通常建议保留排序步骤以确保算法的正确性和鲁棒性。