მინიმალური გადადის მასივის ტოლ ელემენტებზე Leetcode Solution


Რთული ტური Easy
ხშირად ეკითხებიან Amazon Apple Coursera ფაქტები ნამდვილად JPMorgan მათემატიკის სამუშაოები microsoft სვიგი
უჯრა მათემატიკის

პრობლემის განცხადება

ამ პრობლემის დროს ჩვენ გვეძლევა მასივი მთელი რიცხვების. ასევე, ამ მასივზე უფლება გვაქვს შევასრულოთ გარკვეული ოპერაციები. ერთ ოპერაციაში, მასივში შეგვიძლია ”n - 1 elements (ყველა ელემენტის გარდა) ელემენტების გაზრდა 1-ით.

ჩვენ უნდა ვიპოვოთ ოპერაციების მინიმალური რაოდენობა, რაც საჭიროა მასივის ყველა ელემენტის ტოლობისთვის.

მაგალითი

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

 

მინიმალური გადადის მასივის ტოლ ელემენტებზე Leetcode Solutionმიდგომა (მათემატიკა)

ამ პრობლემისას სირთულე იმაში მდგომარეობს, რომ აირჩიო რიცხვების სიმრავლე, რომელთა გაზრდაც 1-ით გსურთ, მასივის ყველა ელემენტის ტოლი იყოს. თუმცა, 'N - 1' ელემენტების მასივში გაზრდა იგივეა, რაც 1 მასივის ელემენტის შემცირება XNUMX-ით. ეს იმიტომ ხდება, რომ არ გვინდა გავარკვიოთ, თუ რა მნიშვნელობა ექნება ყველა ელემენტს, მათი ტოლი ტოლობის შემდეგ, უფრო მეტად ჩვენ დაინტერესებულნი ვართ ვიპოვოთ სვლების რაოდენობა. ახლა ეს ინტუიტიურია, რომ რადგან ჩვენი მოქმედებაა მასივის ზუსტად ერთი ელემენტის შემცირება 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;
}

ჯავა პროგრამა

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 Solution

დროის სირთულე

O (N), N = მასივის ზომა. ჩვენ ერთხელ გადავკვეთთ მასივს.

სივრცის სირთულე 

O (1), რადგან მასივში ვიყენებთ მეხსიერების მუდმივ ადგილს.