Минимално премештање једнаког низа елемената Леетцоде решење


Ниво тешкоће Лако
Често питани у амазонка јабука Цоурсера Фацтсет Заиста ЈПМорган Матхворкс мицрософт Свигги
Дравбридге Математика

Изјава о проблему

У овом проблему добијамо поредак целих бројева. Такође, дозвољено нам је да извршимо одређени скуп операција над овим низом. У једној операцији можемо повећати елементе „н - 1 ″ (сви елементи осим било ког) у низу за 1.

Морамо пронаћи минимални број операција потребних да би се сви елементи низа изједначили.

Пример

Array = {1 , 2 , 3}
3
Array = {1 , 1 , 1}
0

 

Минимално премештање једнаког низа елемената Леетцоде решењеПриступ (математика)

У овом проблему потешкоћа је у одабиру скупа бројева које бисте желели да повећате за 1 да би се изједначили сви елементи низа. Међутим, повећање елемената „Н - 1“ у низу је исто као смањење једног елемента низа за 1. То је зато што не желимо да сазнамо колика ће бити вредност свих елемената када су једнаки, већ нас занима тражење броја потеза. Ово је интуитивно да, пошто наша операција треба да смањи тачно један елемент у низу за 1, морамо да претворимо све елементе у низу у минимални елемент присутан у низу (пошто га не треба смањивати даље).

Имплементација за минимално премештање у једнаке елементе низа Леетцоде решење

Програм Ц ++

#include <bits/stdc++.h>

using namespace std;

int minMoves(vector <int> nums) {
    int mn = *min_element(nums.begin() , nums.end()) , moves = 0;
    for(int &i : nums)
        moves += i - mn;
    return moves;
}

int main() {
    vector <int> nums = {1 , 2 , 3};
    cout << minMoves(nums) << endl;
    return 0;
}

Јава Програм

import java.lang.*;
import java.util.*;

class min_moves {
    public static void main(String args[]) {
        int[] nums = {1 , 2 , 3};
        System.out.println(minMoves(nums));
    }

    public static int minMoves(int[] nums) {
        if(nums.length == 0)
            return 0;
        int mn = nums[0];
        for(int i = 0 ; i < nums.length ; i++) {
            mn = Math.min(mn , nums[i]);
        }

        int moves = 0;
        for(int i = 0 ; i < nums.length ; i++) {
            moves += nums[i] - mn;
        }

        return moves;
    }
}
3

Анализа сложености минималних потеза ка једнаким елементима низа Решење Леетцоде

Сложеност времена

НА), Н = величина низа. Једном пређемо цео низ.

Сложеност простора 

О (1), јер користимо константни меморијски простор у низу.