LeetCode 2740.找出分区值：排序

【LetMeFly】2740.找出分区值：排序

力扣题目链接：https://leetcode.cn/problems/find-the-value-of-the-partition/

给你一个 正 整数数组

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

解题方法：排序

这个要求的绝对值之差的最小值，有没有可能就是原始数组中任意两个数绝对值之差的最小值呢？

答案是Yes。假设原始数组中a和b的绝对值之差最小。

• 如果a小于b，那么我们可以将所有小于等于a的元素分到一个数组中，将所有大于等于b的元素分到一个数组中。而一定不存在大于a且小于b的元素（否则a与b的绝对值之差一定不会是最小），完美。
• 如果a大于b，同理。
• 如果a等于b，将所有小于等于a的元素分到第一个数组中，将所有大于a的元素分到第二个数组中，再从第一个数组中拿出一个a放到第二个数组中，完美。

如何求元素数组中任意两个数绝对值之差的最小值？

只需将原始数组从小到大排序，所有相邻两元素的绝对值之差的最小值即为所求。

其实可以发现，这个问题的实质就是对原始数组排序，之后选择一个位置切一刀，就分成了两个数组。问你在哪里切会使被分开的两个元素之差的绝对值最小。

• 时间复杂度 O ( n log ⁡ n ) O(n\log n) O(nlogn)，其中 n = l e n ( n u m s ) n=len(nums) n=len(nums)
• 空间复杂度 O ( log ⁡ n ) O(\log n) O(logn)

AC代码

以下代码中都多了一个无用操作：取绝对值。因为排序后后面元素一定不小于前面元素，因此可以不用求

nums[i] - nums[i - 1]

的绝对值。

但这丝毫不影响Java的提交时间击败100.00%空间击败97.03%(bushi)

C++

classSolution{public:intfindValueOfPartition(vector<int>& nums){sort(nums.begin(), nums.end());int ans =1'000'000'000;for(int i =1; i < nums.size(); i++){
            ans =min(ans,abs(nums[i]- nums[i -1]));}return ans;}};

Go

package main

import"sort"funcmin(a int, b int)int{if a <= b {return a
    }return b
}funcabs(a int)int{if a >=0{return a
    }return-a
}funcfindValueOfPartition(nums []int)int{
    sort.Ints(nums);
    ans :=1000000000;for i :=1; i <len(nums); i++{
        ans =min(ans,abs(nums[i]- nums[i -1]))}return ans;}

Java

importjava.util.Arrays;classSolution{publicintfindValueOfPartition(int[] nums){Arrays.sort(nums);int ans =1000000000;for(int i =1; i < nums.length; i++){
            ans =Math.min(ans,Math.abs(nums[i]- nums[i -1]));}return ans;}}

Python

from typing import List

classSolution:deffindValueOfPartition(self, nums: List[int])->int:
        nums.sort()returnmin(abs(nums[i]- nums[i -1])for i inrange(1,len(nums)))

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/140717473