462. Minimum Moves to Equal Array Elements II

leetcode medium

#array#bit-manipulation#csharp#leetcode#math#medium

Task

Дан массив целых чисел nums размера n, вернуть минимальное количество ходов, необходимых для того, чтобы сделать все элементы массива равными.

В одном ходе вы можете увеличить или уменьшить элемент массива на 1.

Тестовые случаи составлены так, что ответ поместится в 32-битное целое число.

Пример:

Input: nums = [1,2,3]

Output: 2

Explanation:

Only two moves are needed (remember each move increments or decrements one element):

[1,2,3] => [2,2,3] => [2,2,2]

C# solution

matched/original

public class Solution {
    public int MinMoves2(int[] nums) {
        long ans = long.MaxValue;
        int minval = int.MaxValue;
        int maxval = int.MinValue;
        foreach (int num in nums) {
            minval = Math.Min(minval, num);
            maxval = Math.Max(maxval, num);
        }
        for (int i = minval; i <= maxval; i++) {
            long sum = 0;
            foreach (int num in nums) {
                sum += Math.Abs(num - i);
            }
            ans = Math.Min(ans, sum);
        }
        return (int) ans;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MinMoves2(vector<int>& nums) {
        long ans = long.MaxValue;
        int minval = int.MaxValue;
        int maxval = int.MinValue;
        foreach (int num in nums) {
            minval = min(minval, num);
            maxval = max(maxval, num);
        }
        for (int i = minval; i <= maxval; i++) {
            long sum = 0;
            foreach (int num in nums) {
                sum += abs(num - i);
            }
            ans = min(ans, sum);
        }
        return (int) ans;
    }
}

Java solution

matched/original

public class Solution {
    public int minMoves2(int[] nums) {
        long ans = Long.MAX_VALUE;
        int minval = Integer.MAX_VALUE;
        int maxval = Integer.MIN_VALUE;
        for (int num : nums) {
            minval = Math.min(minval, num);
            maxval = Math.max(maxval, num);
        }
        for (int i = minval; i <= maxval; i++) {
            long sum = 0;
            for (int num : nums) {
                sum += Math.abs(num - i);
            }
            ans = Math.min(ans, sum);
        }
        return (int) ans;
    }
}

JavaScript solution

matched/original

class Solution {
    minMoves2(nums) {
        let ans = Number.MAX_SAFE_INTEGER;
        let minval = Math.min(...nums);
        let maxval = Math.max(...nums);
        for (let i = minval; i <= maxval; i++) {
            let sum = 0;
            for (let num of nums) {
                sum += Math.abs(num - i);
            }
            ans = Math.min(ans, sum);
        }
        return ans;
    }
}

Python solution

matched/original

class Solution:
    def minMoves2(self, nums: List[int]) -> int:
        ans = float('inf')
        minval = min(nums)
        maxval = max(nums)
        for i in range(minval, maxval + 1):
            sum_moves = 0
            for num in nums:
                sum_moves += abs(num - i)
            ans = min(ans, sum_moves)
        return int(ans)

Go solution

matched/original

package main

import (
    "math"
    "sort"
)

func minMoves2(nums []int) int {
    ans := math.MaxInt64
    minval, maxval := nums[0], nums[0]
    for _, num := range nums {
        if num < minval {
            minval = num
        }
        if num > maxval {
            maxval = num
        }
    }
    for i := minval; i <= maxval; i++ {
        sum := 0
        for _, num := range nums {
            sum += int(math.Abs(float64(num - i)))
        }
        if sum < ans {
            ans = sum
        }
    }
    return ans
}

Explanation

Algorithm

Найти минимальный и максимальный элементы в массиве. Пусть k будет числом, к которому должны быть приведены все элементы массива.

Перебирать значения k в диапазоне между минимальным и максимальным элементами, вычисляя количество ходов, необходимых для каждого k.

Определить минимальное количество ходов среди всех возможных k, что и будет конечным результатом.

😎