Массивын элементүүдийг тэнцүү болгох хамгийн бага алхам Leetcode шийдэл  


Хэцүү байдлын түвшин Easy
Байнга асуудаг Амазоны Apple-ийн Coursera Мэдээллийн багц Үнэндээ JPMorgan Математикийн ажил Microsoft- Swiggy
алгоритмууд кодлох Зурах гүүр ярилцлага ярилцлагын бэлтгэл LeetCode LeetCodeSolutions Математик

Асуудлын мэдэгдэл  

Энэ асуудалд бидэнд массив бүхэл тоонууд. Түүнчлэн, бид энэ массив дээр тодорхой багц үйлдлийг хийхийг зөвшөөрдөг. Нэг үйлдэл дээр бид массив дахь ”n - 1 ″ (бусад бүх элементүүд) элементүүдийг 1-ээр нэмэгдүүлэх боломжтой.

Массивын бүх элементүүдийг тэнцүү болгохын тулд шаардлагатай үйлдлүүдийн хамгийн бага тоог олох хэрэгтэй.

Жишээ нь

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

 

Массивын элементүүдийг тэнцүү болгох хамгийн бага алхам Leetcode шийдэлPinХандалт (Математик)  

Энэ асуудалд бүх массивын элементүүдийг тэнцүү болгохын тулд 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 Solution

Цаг хугацааны нарийн төвөгтэй байдал

O (N), N = массивын хэмжээ. Бид массивыг бүхэлд нь нэг удаа туулдаг.

мөн үзнэ үү
Monotonic Array LeetCode шийдэл

Сансрын нарийн төвөгтэй байдал 

O (1), бид массивт тогтмол санах ойн зайг ашигладаг тул.

1