[アルゴリズム]LeetCode-Mimimum Difference Between LargestとSmallest Value in Three Moves
LeetCode - 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.
I/O例
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.
せいげんじょうけん
1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
Solution
[戦略]
1.アレイ内の要素数が4個未満の場合は、1つの値に統一できるため、常に最小差は0
2.アレイを並べ替えて、3つの値を変更したときの最小差候補値を得る
3.最小差を達成するには、配列内の小さな値を増やすか、大きな値を小さくする必要があります.ex) [6,6,0,1,1,4,6]
0 1 1 4 6 6 6
. .
. .
. .
. .
import java.util.*;
class Solution {
public int minDifference(int[] nums) {
int numsLen = nums.length;
if (numsLen <= 4) {
return 0;
}
Arrays.sort(nums);
int min = nums[numsLen - 1] - nums[0];
for (int i = 0; i <= 3; i++) {
min = Math.min(min, nums[numsLen - 4 + i] - nums[i]);
}
return min;
}
}
Reference
この問題について([アルゴリズム]LeetCode-Mimimum Difference Between LargestとSmallest Value in Three Moves), 我々は、より多くの情報をここで見つけました
https://velog.io/@jerry92/알고리즘-LeetCode-Minimum-Difference-Between-Largest-and-Smallest-Value-in-Three-Moves
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
ex) [6,6,0,1,1,4,6]
0 1 1 4 6 6 6
. .
. .
. .
. .
import java.util.*;
class Solution {
public int minDifference(int[] nums) {
int numsLen = nums.length;
if (numsLen <= 4) {
return 0;
}
Arrays.sort(nums);
int min = nums[numsLen - 1] - nums[0];
for (int i = 0; i <= 3; i++) {
min = Math.min(min, nums[numsLen - 4 + i] - nums[i]);
}
return min;
}
}
Reference
この問題について([アルゴリズム]LeetCode-Mimimum Difference Between LargestとSmallest Value in Three Moves), 我々は、より多くの情報をここで見つけました https://velog.io/@jerry92/알고리즘-LeetCode-Minimum-Difference-Between-Largest-and-Smallest-Value-in-Three-Movesテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol