Минимални премествания към решения с равни масиви Leetcode Solution


Ниво на трудност Лесно
Често задавани в Амазонка ябълка Coursera FactSet Наистина JPMorgan Математика Microsoft Swiggy
Подвижен мост Математически

Декларация за проблема

В този проблем ни се дава масив на цели числа. Също така ни е позволено да изпълняваме определен набор от операции върху този масив. В една операция можем да увеличим “n - 1 ″ (всички елементи с изключение на която и да е) елементи в масива с 1.

Трябва да намерим минималния брой операции, необходими, за да направим всички елементи на масива равни.

Пример

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

 

Минимални премествания към решения с равни масиви Leetcode SolutionПодход (математика)

При този проблем трудността е да изберете набора от числа, които бихте искали да увеличите с 1, за да се изравнят всички елементи на масива. Въпреки това, увеличаването на елементите „N - 1“ в масива е същото като намаляването на един елемент на масива с 1. Това е така, защото не искаме да разберем каква ще бъде стойността на всички елементи, след като те са равни, а се интересуваме от намирането на броя ходове. Това е интуитивно, че тъй като нашата операция е да намалим точно един елемент в масива с 1, трябва да преобразуваме всички елементи в масива в минималния елемент, присъстващ в масива (тъй като не е необходимо да се намалява по-нататък).

Внедряване за минимални премествания към решения с равни масиви Leetcode Solution

Програма 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 решение

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

НА), N = размер на масива. Преминаваме веднъж целия масив.

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

O (1), тъй като използваме постоянно пространство в паметта в масива.