העברות מינימליות לפתרון Leetcode של אלמנטים מערכים שווים  


רמת קושי קַל
נשאל לעתים קרובות אמזון בעברית תפוח עץ Coursera סט עובדות אכן פי מורגן עבודות מתמטיקה מיקרוסופט Swiggy
אלגוריתמים קידוד Drawbridge ראיון אישי הוכחת ראיונות LeetCode LeetCodeSolutions מתמטיקה

הצהרת בעיה  

בבעיה זו ניתן לנו מערך של מספרים שלמים. כמו כן, אנו רשאים לבצע קבוצה מסוימת של פעולות במערך זה. בפעולה אחת נוכל להגדיל את האלמנטים "n - 1 ″ (כל האלמנטים למעט כל אחד) במערך ב -1.

עלינו למצוא את מספר הפעולות המינימלי הנדרש בכדי להפוך את כל רכיבי המערך לשווים.

דוגמה

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

 

העברות מינימליות לפתרון Leetcode של אלמנטים מערכים שוויםגישה (מתמטיקה)  

בבעיה זו, הקושי הוא לבחור את קבוצת המספרים שתרצה להגדיל ב- 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 של מרכיבי מערך שווים

מורכבות זמן

עַל), N = גודל המערך. אנו חוצים את כל המערך פעם אחת.

ראה גם
פתרון מערך מונוטוני LeetCode

מורכבות בחלל 

O (1), כאשר אנו משתמשים במרחב זיכרון קבוע במערך.