Массив элементтеріне тең минималды жылжу парақ кодының шешімі  


Күрделілік дәрежесі оңай
Жиі кіреді Amazon алма Coursera Деректер жинағы шынында JPMorgan Математика Microsoft Swiggy
алгоритмдер кодтау Кескіш сұхбат сұхбат дайындау LeetCode LeetCodeSolutions математика

Проблемалық мәлімдеме  

Бұл мәселеде бізге ан массив бүтін сандар. Сондай-ақ, бізге осы жиым бойынша белгілі бір амалдар жиынтығын жасауға рұқсат етіледі. Бір әрекетте біз массивтегі элементтерді n - 1 ″ (кез келгенінен басқа барлық элементтер) ұлғайта аламыз.

Біз барлық массив элементтерін тең ету үшін қажетті минималды операцияларды табуымыз керек.

мысал

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

 

Массив элементтеріне тең минималды жылжу парақ кодының шешіміТәсіл (математика)  

Бұл мәселеде барлық массив элементтеріне тең болу үшін 1-ге арттырғыңыз келетін сандар жиынын таңдау қиын. Алайда, жиымдағы 'N - 1' элементтерін көбейту бір массив элементтерін 1-ге кеміткенмен бірдей. Себебі, біз барлық элементтер тең болғаннан кейін олардың мәні қандай болатынын білгіміз келмейді, керісінше жүріс санын табуға мүдделіміз. Енді интуитивті, бұл біздің жұмысымыз массивтегі бір элементті 1-ге азайту болғандықтан, массивтегі барлық элементтерді массивтегі минималды элементке айналдыруымыз керек (өйткені оны азайтудың қажеті жоқ) әрі қарай).

Тең массив элементтеріне минималды жылжуларды енгізу Leetcode шешімі

C ++ бағдарламасы

#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;
}

Java бағдарламасы

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

Массивтің тең элементтеріне минималды қозғалыстардың күрделілігін талдау Leetcode шешімі

Уақыттың күрделілігі

O (N), N = массивтің өлшемі. Біз бүкіл массивті бір рет айналып өтеміз.

Сондай-ақ, қараңыз
Monetonic Array LeetCode шешімі

Ғарыштың күрделілігі 

O (1), біз массивте тұрақты жад кеңістігін қолданған кезде.