题目描述
给你一个 正 整数数组 nums
。
将 nums
分成两个数组:nums1
和 nums2
,并满足下述条件:
- 数组
nums
中的每个元素都属于数组nums1
或数组nums2
。 - 两个数组都 非空。
- 分区值 最小。
分区值的计算方法是 |max(nums1) - min(nums2)|
。
其中,max(nums1)
表示数组 nums1
中的最大元素,min(nums2)
表示数组 nums2
中的最小元素。
返回表示分区值的整数。
样例
输入:nums = [1,3,2,4]
输出:1
解释:可以将数组 nums 分成 nums1 = [1,2] 和 nums2 = [3,4]。
- 数组 nums1 的最大值等于 2。
- 数组 nums2 的最小值等于 3。
分区值等于 |2 - 3| = 1。
可以证明 1 是所有分区方案的最小值。
输入:nums = [100,1,10]
输出:9
解释:可以将数组 nums 分成 nums1 = [10] 和 nums2 = [100,1]。
- 数组 nums1 的最大值等于 10。
- 数组 nums2 的最小值等于 1。
分区值等于 |10 - 1| = 9。
可以证明 9 是所有分区方案的最小值。
限制
2 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
算法
(思维题) $O(n \log n)$
- 一个显然的思路是将
nums
数组排序,然后从某个位置分割,这样可以保证最优条件。 - 所以最终答案就是排序后数组中,相邻元素的最小值。
时间复杂度
- 排序的时间复杂度为 $O(n \log n)$。
- 排序后,需要 $O(n)$ 的时间求解答案。
- 故总时间复杂度为 $O(n \log n)$。
空间复杂度
- 需要 $O(\log n)$ 的额外空间存储排序的系统栈。
C++ 代码
class Solution {
public:
int findValueOfPartition(vector<int>& nums) {
const int n = nums.size();
sort(nums.begin(), nums.end());
int ans = INT_MAX;
for (int i = 1; i < n; i++)
ans = min(ans, nums[i] - nums[i - 1]);
return ans;
}
};
dalao 题解放错了?
已修复