Equal Array Elements Leetcode 솔루션으로의 최소 이동

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

이 문제에서 우리는 정렬 정수 또한이 배열에서 특정 작업을 수행 할 수 있습니다. 한 번의 작업으로 배열의”n – 1 ″ (하나를 제외한 모든 요소) 요소를 1 씩 증가시킬 수 있습니다.

모든 배열 요소를 동일하게 만드는 데 필요한 최소 연산 수를 찾아야합니다.

예

Array = {1 , 2 , 3}

3

Array = {1 , 1 , 1}

0

 

핀접근 (수학)

이 문제에서 어려움은 모든 배열 요소를 동일하게하기 위해 1 씩 증가시킬 숫자 세트를 선택하는 것입니다. 하나, 배열에서 'N – 1'요소를 늘리는 것은 하나의 배열 요소를 1 씩 줄이는 것과 같습니다. 이는 모든 요소가 같을 때 어떤 값이 될지 알아 내고 싶지 않고, 이동 횟수를 찾는 데 관심이 있기 때문입니다. 자, 이것은 우리의 작업이 배열에서 정확히 하나의 요소를 1 씩 줄이는 것이므로, 배열의 모든 요소를 ​​배열에 존재하는 최소 요소로 변환해야한다는 점이 직관적입니다 (줄일 필요가 없으므로 더욱이).

Equal Array Elements 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;
}

자바 프로그램

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

Equal Array Elements Leetcode 솔루션에 대한 최소 이동의 복잡성 분석

시간 복잡성

의 위에), N = 배열의 크기. 전체 배열을 한 번 횡단합니다.

공간 복잡성 

O (1), 배열에서 일정한 메모리 공간을 사용하기 때문입니다.