ขั้นต่ำการย้ายไปยัง Equal Array Elements Leetcode Solution  


ระดับความยาก สะดวกสบาย
ถามบ่อยใน อเมซอน แอปเปิล Coursera ข้อเท็จจริง จริง JPMorgan คณิตศาสตร์ ไมโครซอฟท์ Swiggy
อัลกอริทึม การเข้ารหัส สะพานชัก สัมภาษณ์ สัมภาษณ์เตรียม LeetCode LeetCodeSolutions คณิตศาสตร์

คำชี้แจงปัญหา  

ในปัญหานี้เราจะได้รับไฟล์ แถว จำนวนเต็ม นอกจากนี้เรายังได้รับอนุญาตให้ดำเนินการบางชุดกับอาร์เรย์นี้ ในการดำเนินการเดียวเราสามารถเพิ่ม” n - 1″ (องค์ประกอบทั้งหมดยกเว้นองค์ประกอบใด ๆ ) ในอาร์เรย์ได้ 1

เราต้องหาจำนวนการดำเนินการขั้นต่ำที่จำเป็นเพื่อให้องค์ประกอบอาร์เรย์ทั้งหมดเท่ากัน

ตัวอย่าง

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

 

ขั้นต่ำการย้ายไปยัง Equal Array Elements Leetcode Solutionแนวทาง (คณิตศาสตร์)  

ในปัญหานี้ความยากคือการเลือกชุดตัวเลขที่คุณต้องการเพิ่มขึ้น 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

ความซับซ้อนของเวลา

บน), N = ขนาดของอาร์เรย์ เราสำรวจอาร์เรย์ทั้งหมดหนึ่งครั้ง

ดูสิ่งนี้ด้วย
โซลูชัน LeetCode อาร์เรย์โมโนโทนิก

ความซับซ้อนของอวกาศ 

O (1)เนื่องจากเราใช้พื้นที่หน่วยความจำคงที่ในอาร์เรย์