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)$，其中$n=len(nums)$
• 空间复杂度$O(\log n)$

AC代码

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

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

C++

class Solution {
public:
    int findValueOfPartition(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"

func min(a int, b int) int {
    if a <= b {
        return a
    }
    return b
}

func abs(a int) int {
    if a >= 0 {
        return a
    }
    return -a
}

func findValueOfPartition(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

import java.util.Arrays;

class Solution {
    public int findValueOfPartition(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

class Solution:
    def findValueOfPartition(self, nums: List[int]) -> int:
        nums.sort()
        return min(abs(nums[i] - nums[i - 1]) for i in range(1, len(nums)))

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

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