Leetcode每日一题 202040726 2740.找出分区值

题目描述

给你一个 正 整数数组 nums 。
将 nums 分成两个数组：nums1 和 nums2 ，并满足下述条件：

• 数组 nums 中的每个元素都属于数组 nums1 或数组 nums2 。
• 两个数组都 非空 。
• 分区值 最小 。
  分区值的计算方法是 |max(nums1) - min(nums2)| 。

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

返回表示分区值的整数。
2740.找出分区值

测试案例及提示

示例 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⁵
1 <= nums[i] <= 10⁹

解题思路

读题，剖析题意。

①数组 nums 中的每个元素都属于数组 nums1 或数组 nums2。说明我们在分nums1和nums2时，不能去除元素，必须把nums中的元素都分给num1和nums2之一。
②两个数组都 非空。说明两部分都必须至少有一个元素，不能没有元素。从分区值的计算公式也可看出，要是nums1/nums2其中一个为为空，那这一部分就无从计算max或者是min了。
③分区值 最小 。结合计算公式，我们知道需要找到两部分，一部分的最大值和另外一部分的最小值相差最小。

看示例，进一步理解。

nums = [1,3,2,4]，可以将数组 nums 分成 nums1 = [1,2] 和 nums2 = [3,4] 。说明nums1与nums2不必连续，可以跳跃式选值。

理解后，明确思路。

既然nums1和nums2是可以直接从nums中选择，而且要求一部分的最大值与另一部分的最小值相差最小。因此直接对nums排序，依次遍历每一个元素，计算与后一个元素的差值（这两个元素分别看作是nums1的最大值与nums2的最小值），然后不断更新差值的最小值，即是最小的分区值。
（如果最小的差值为0，即可直接返回0，减少后续无效判断）
python

class Solution:
    def findValueOfPartition(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        Min = float('inf')
        for i in range(n - 1):
            Min = min(Min, (nums[i + 1] - nums[i]))
            if Min == 0:
                return 0
        return Min

C

int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

int Min(int a, int b) { 
    return a <= b ? a : b;
}

int findValueOfPartition(int* nums, int numsSize){
    qsort(nums, numsSize, sizeof(int), compare);
    long min = (1e9 + 1);
    for (int i = 0; i < numsSize - 1; i++) {
        min = Min(min, (nums[i + 1] - nums[i]));
        if (min == 0) {
            return 0;
        }
    }
    return min;
}