[LeetCode] 1509. Minimum Difference Between Largest and Smallest Value in Three Moves
2021/8/20 6:36:56
本文主要是介绍[LeetCode] 1509. Minimum Difference Between Largest and Smallest Value in Three Moves,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Given an array nums
, you are allowed to choose one element of nums
and change it by any value in one move.
Return the minimum difference between the largest and smallest value of nums
after perfoming at most 3 moves.
Example 1:
Input: nums = [5,3,2,4] Output: 0 Explanation: Change the array [5,3,2,4] to [2,2,2,2]. The difference between the maximum and minimum is 2-2 = 0.
Example 2:
Input: nums = [1,5,0,10,14] Output: 1 Explanation: Change the array [1,5,0,10,14] to [1,1,0,1,1]. The difference between the maximum and minimum is 1-0 = 1.
Example 3:
Input: nums = [6,6,0,1,1,4,6] Output: 2
Example 4:
Input: nums = [1,5,6,14,15] Output: 1
Constraints:
1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
三次操作后最大值与最小值的最小差。
给你一个数组 nums ,每次操作你可以选择 nums 中的任意一个元素并将它改成任意值。
请你返回三次操作后, nums 中最大值与最小值的差的最小值。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/minimum-difference-between-largest-and-smallest-value-in-three-moves
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
这道题可以排序做,也可以不排序做,但是不排序的代码太过麻烦,排序的做法实现起来会简单很多。
题意要求的是在给定的 input 数组里去掉三个数字,使得剩下的数字的最大值 - 最小值的差值最小。这道题的 corner case 是如果数组长度小于 5,那么基本就不需要比较了。如果数组长度大于 5,我们才需要找到最大的 4 个数字和最小的 4 个数字。所以直觉是需要排序,然后比较到底是去掉
- 最小的三个数字
- 最大的三个数字
- 最小的一个 + 最大的两个
- 最小的两个 + 最大的一个
时间O(nlogn)
空间O(1)
Java实现
1 class Solution { 2 public int minDifference(int[] nums) { 3 int len = nums.length; 4 // corner case 5 if (len <= 4) { 6 return 0; 7 } 8 9 // normal case 10 Arrays.sort(nums); 11 int res = Integer.MAX_VALUE; 12 for (int i = 0; i < 4; i++) { 13 res = Math.min(res, nums[len - 4 + i] - nums[i]); 14 } 15 return res; 16 } 17 }
我这里提供一个讨论区看到的不排序的做法,但是为了找到最大的4个数字和最小的4个数字,这个做法还是需要利用到堆来筛选,再加上元素在堆操作的进出,其实最后代码跑下来的速度还不如直接排序来得快。
时间O(nlogn)
空间O(n)
Java实现
1 class Solution { 2 public int minDifference(int[] nums) { 3 // corner case 4 if (nums.length < 5) { 5 return 0; 6 } 7 if (nums.length <= 8) { 8 return helper(nums, true); 9 } 10 PriorityQueue<Integer> top4 = new PriorityQueue<>(); 11 PriorityQueue<Integer> bottom4 = new PriorityQueue<>((a, b) -> b - a); 12 for (int n : nums) { 13 top4.offer(n); 14 bottom4.offer(n); 15 if (top4.size() > 4) { 16 top4.poll(); 17 } 18 if (bottom4.size() > 4) { 19 bottom4.poll(); 20 } 21 } 22 int[] arr = new int[8]; 23 for (int l = 3, r = 4; l >= 0 && r < 8; l--, r++) { 24 arr[l] = bottom4.poll(); 25 arr[r] = top4.poll(); 26 } 27 return helper(arr, false); 28 } 29 30 private int helper(int[] nums, boolean needSort) { 31 if (needSort) { 32 Arrays.sort(nums); 33 } 34 int res = Integer.MAX_VALUE; 35 int n = nums.length; 36 for (int i = 0; i < 4; i++) { 37 res = Math.min(res, nums[n - (4 - i)] - nums[i]); 38 } 39 return res; 40 } 41 }
LeetCode 题目总结
这篇关于[LeetCode] 1509. Minimum Difference Between Largest and Smallest Value in Three Moves的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-06Package Easy(基于 NSIS 的打包exe安装包工具)使用方法-icode9专业技术文章分享
- 2024-06-06基于 casdoor 的 ELK 开源登录认证解决方案: elk-auth-casdoor-icode9专业技术文章分享
- 2024-05-29Elasticsearch慢查询日志配置
- 2024-05-29揭秘华为如此多成功项目的产品关键——Charter模板
- 2024-05-29海外IDC业务拓展的7大挑战
- 2024-05-29InLine Chat功能优化对标Github Copilot,CodeGeeX带来更高效、更直观的编程体验!
- 2024-05-29CodeGeeX 智能编程助手 6 项功能升级,在Visual Studio插件市场霸榜2周!
- 2024-05-29AutoMQ 生态集成 Apache Doris
- 2024-05-292024年IDC行业的深度挖掘:机遇、挑战与未来展望
- 2024-05-29五款扩展组件齐发 —— Volcano、Keda、Crane-scheduler 等,邀你体验