找出分区值
难度:
标签:
题目描述
You are given a positive integer array nums.
Partition nums into two arrays, nums1 and nums2, such that:
- Each element of the array
numsbelongs to either the arraynums1or the arraynums2. - Both arrays are non-empty.
- The value of the partition is minimized.
The value of the partition is |max(nums1) - min(nums2)|.
Here, max(nums1) denotes the maximum element of the array nums1, and min(nums2) denotes the minimum element of the array nums2.
Return the integer denoting the value of such partition.
Example 1:
Input: nums = [1,3,2,4] Output: 1 Explanation: We can partition the array nums into nums1 = [1,2] and nums2 = [3,4]. - The maximum element of the array nums1 is equal to 2. - The minimum element of the array nums2 is equal to 3. The value of the partition is |2 - 3| = 1. It can be proven that 1 is the minimum value out of all partitions.
Example 2:
Input: nums = [100,1,10] Output: 9 Explanation: We can partition the array nums into nums1 = [10] and nums2 = [100,1]. - The maximum element of the array nums1 is equal to 10. - The minimum element of the array nums2 is equal to 1. The value of the partition is |10 - 1| = 9. It can be proven that 9 is the minimum value out of all partitions.
Constraints:
2 <= nums.length <= 1051 <= nums[i] <= 109
代码结果
运行时间: 97 ms, 内存: 27.4 MB
/*
* 思路：
* 1. 将数组进行排序。
* 2. nums1取前n个元素，nums2取剩余的元素。
* 3. 因为数组是有序的，所以nums1的最大值是nums[n/2-1]，nums2的最小值是nums[n/2]。
* 4. 计算二者的差值即为最小的分区值。
*/
import java.util.Arrays;
public class Solution {
public int minPartitionValue(int[] nums) {
return Arrays.stream(nums).sorted().boxed()
.collect(Collectors.collectingAndThen(Collectors.toList(), sortedList -> {
int n = sortedList.size();
int maxNums1 = sortedList.get(n / 2 - 1);
int minNums2 = sortedList.get(n / 2);
return Math.abs(maxNums1 - minNums2);
}));
}
}解释
方法:
该题解通过首先对数组进行排序，然后计算相邻元素之间的最小差值来实现。因为在一个排序的数组中，两个子数组最优分割点就在最小的差值的两个元素之间，即这两个元素分别是两个子数组中的边界元素。这样可以保证计算出来的 |max(nums1) - min(nums2)| 最小。
时间复杂度:
O(n log n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在这个问题中，排序数组后计算相邻元素的最小差值就能保证找到最小的分区值？
▷🦆
在实现中，为什么初始化最小差值 `a` 为数组中第一个元素和第二个元素的差，而不是设置为更大的值或其他元素的差？
▷🦆
如果数组 `nums` 的长度非常小，比如只有两个元素，这种方法是否仍然有效，并且能得到正确的输出？
▷🦆
如果输入数组 `nums` 已经是排序状态，是否有必要再次进行排序，或者我们可以直接跳到计算相邻元素差值的步骤？
▷