排序、最小值，基于排序获取中位数，求解《1887. 使数组元素相等的减少操作次数》《453. 最小操作次数使数组元素相等》和《462. 最少移动次数使数组元素相等 II》
降序
- Java 降序：int[] - Integer[]：转换为 stream 装箱，转数组：
Arrays.stream(nums).boxed().toArray(Integer[]::new) - Golang 降序：
sort.Sort(sort.Reverse(sort.IntSlice(nums))) - Python 降序：
nums.sort(reverse = True)
例题
1887. 使数组元素相等的减少操作次数
给你一个整数数组 nums ，你的目标是令 nums 中的所有元素相等。完成一次减少操作需要遵照下面的几个步骤：
找出 nums 中的 最大 值。记这个值为 largest 并取其下标 i （下标从 0 开始计数）。如果有多个元素都是最大值，则取最小的 i 。
找出 nums 中的 下一个最大 值，这个值 严格小于 largest ，记为 nextLargest 。
将 nums[i] 减少到 nextLargest 。
返回使 nums 中的所有元素相等的操作次数。
答案
升序
var reductionOperations = function(nums) {
const n = nums.length
nums.sort((a, b) => a - b)
let r = 0
for (let i = 1; i < n; i++) {
if (nums[i - 1] !== nums[i]) r += n - i
}
return r
};function reductionOperations(nums: number[]): number {
const n = nums.length
nums.sort((a, b) => a - b)
let r = 0
for (let i = 1; i < n; i++) {
if (nums[i - 1] !== nums[i]) r += n - i
}
return r
};func reductionOperations(nums []int) int {
n, r := len(nums), 0
sort.Ints(nums)
for i := 1; i < n; i++ {
if nums[i - 1] != nums[i] {
r += n - i
}
}
return r
}class Solution {
function reductionOperations($nums) {
$n = count($nums);
usort($nums, function($a, $b) {
return $a > $b;
});
$r = 0;
for ($i = 1; $i < $n; $i++) {
if ($nums[$i - 1] !== $nums[$i]) $r += $n - $i;
}
return $r;
}
}class Solution:
def reductionOperations(self, nums: List[int]) -> int:
n, r = len(nums), 0
nums.sort()
for i in range(1, n):
if nums[i - 1] != nums[i]:
r += n - i
return rclass Solution {
public int reductionOperations(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
int r = 0;
for (int i = 1; i < n; i++) {
if (nums[i - 1] != nums[i]) r += n - i;
}
return r;
}
}降序
var reductionOperations = function(nums) {
const n = nums.length
nums.sort((a, b) => b - a)
let r = 0
for (let i = 1; i < n; i++) {
if (nums[i - 1] !== nums[i]) r += i
}
return r
};function reductionOperations(nums: number[]): number {
const n = nums.length
nums.sort((a, b) => b - a)
let r = 0
for (let i = 1; i < n; i++) {
if (nums[i - 1] !== nums[i]) r += i
}
return r
};func reductionOperations(nums []int) int {
n, r := len(nums), 0
sort.Sort(sort.Reverse(sort.IntSlice(nums)))
for i := 1; i < n; i++ {
if nums[i - 1] != nums[i] {
r += i
}
}
return r
}class Solution {
function reductionOperations($nums) {
$n = count($nums);
usort($nums, function($a, $b) {
return $a < $b;
});
$r = 0;
for ($i = 1; $i < $n; $i++) {
if ($nums[$i - 1] !== $nums[$i]) $r += $i;
}
return $r;
}
}class Solution:
def reductionOperations(self, nums: List[int]) -> int:
n, r = len(nums), 0
nums.sort(reverse = True)
for i in range(1, n):
if nums[i - 1] != nums[i]:
r += i
return rclass Solution {
public int reductionOperations(int[] nums) {
int n = nums.length;
Integer[] numsNew = Arrays.stream(nums).boxed().toArray(Integer[]::new);
Arrays.sort(numsNew, (a, b) -> b - a);
int r = 0;
for (int i = 1; i < n; i++) {
if (numsNew[i - 1].equals(numsNew[i]) == false) r += i;
}
return r;
}
}453. 最小操作次数使数组元素相等
给你一个长度为 n 的整数数组，每次操作将会使 n - 1 个元素增加 1 。返回让数组所有元素相等的最小操作次数。 输入：nums = [1,2,3]
输出：3
解释：
只需要3次操作（注意每次操作会增加两个元素的值）：
[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]
答案
最小值
n - 1个元素+1= 1 个元素-1- 所有元素相等 = 所有元素减少到最小值
var minMoves = function(nums) {
const n = nums.length, minNum = Math.min.apply(null, nums)
let r = 0
for (let i = 0; i < n; i++) {
r += nums[i] - minNum
}
return r
};function minMoves(nums: number[]): number {
const n = nums.length, minNum = Math.min.apply(null, nums)
let r = 0
for (let i = 0; i < n; i++) {
r += nums[i] - minNum
}
return r
};func minMoves(nums []int) int {
r, minNum := 0, math.MaxInt64
for _, num := range nums {
if minNum > num {
minNum = num
}
}
for _, num := range nums {
r += num - minNum
}
return r
}class Solution {
function minMoves($nums) {
$minNum = min($nums);
$r = 0;
foreach($nums AS $num) {
$r += $num - $minNum;
}
return $r;
}
}class Solution:
def minMoves(self, nums: List[int]) -> int:
minNum, r = min(nums), 0
for num in nums:
r += num - minNum
return rclass Solution {
public int minMoves(int[] nums) {
int minNum = Arrays.stream(nums).min().getAsInt();
int r = 0;
for (int num : nums) {
r += num - minNum;
}
return r;
}
}462. 最少移动次数使数组元素相等 II
给你一个长度为 n 的整数数组 nums ，返回使所有数组元素相等需要的最少移动数。
在一步操作中，你可以使数组中的一个元素加 1 或者减 1 。
答案
排序 · 中位数
var minMoves2 = function(nums) {
nums.sort((a, b) => a - b)
const n = nums.length, median = n & 1 ? nums[n >> 1] : (nums[n >> 1] + nums[(n >> 1) - 1]) >> 1
let r = 0
for (let i = 0; i < n; i++) {
r += Math.abs(nums[i] - median)
}
return r
};function minMoves2(nums: number[]): number {
nums.sort((a, b) => a - b)
const n = nums.length, median = n & 1 ? nums[n >> 1] : nums[n >> 1] + nums[(n >> 1) - 1] >> 1
let r = 0;
for (let i = 0; i < n; i++) {
r += Math.abs(nums[i] - median)
}
return r
};func minMoves2(nums []int) int {
sort.Ints(nums)
n, r, median := len(nums), 0, 0
if n & 1 == 1 {
median = nums[n >> 1]
} else {
median = (nums[n >> 1] + nums[n >> 1 - 1]) >> 1
}
for _, num := range nums {
r += int(math.Abs(float64(num - median)))
}
return r
}class Solution {
function minMoves2($nums) {
usort($nums, function($a, $b) {
return $a > $b;
});
$n = count($nums);
$median = $n & 1 ? $nums[$n >> 1] : $nums[$n >> 1] + $nums[($n >> 1) - 1] >> 1;
$r = 0;
foreach($nums AS $num) {
$r += abs($num - $median);
}
return $r;
}
}class Solution:
def minMoves2(self, nums: List[int]) -> int:
nums.sort()
n, r = len(nums), 0
median = nums[n >> 1] if n & 1 else nums[n >> 1] + nums[(n >> 1) - 1] >> 1
for num in nums:
r += abs(num - median)
return rclass Solution {
public int minMoves2(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
int median = (n & 1) == 1 ? nums[n >> 1] : nums[n >> 1] + nums[(n >> 1) - 1] >> 1;
int r = 0;
for (int num : nums) {
r += Math.abs(num - median);
}
return r;
}
}
