等しい配列要素への最小移動Leetcodeソリューション


難易度 簡単に
よく聞かれる Amazon (アマゾン) Apple Coursera ファクトセット 確かに JPモルガン Mathworks社 マイクロソフト Swiggy
Drawbridge 数学

問題文

この問題では、 配列 整数の。 また、この配列に対して特定の一連の操作を実行することも許可されています。 1回の操作で、配列内の” n – 1”(いずれかXNUMXつを除くすべての要素)要素をXNUMXつインクリメントできます。

すべての配列要素を等しくするために必要な操作の最小数を見つける必要があります。

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

 

等しい配列要素への最小移動Leetcodeソリューションアプローチ(数学)

この問題では、すべての配列要素と等しくなるように1ずつ増やしたい数値のセットを選択するのが困難です。 しかしながら、 配列内の「N– 1」要素を増やすことは、1つの配列要素をXNUMX減らすことと同じです。 これは、すべての要素が等しくなったときにその値がどうなるかを知りたくないためです。むしろ、移動の数を見つけることに関心があります。 これは、配列内の1つの要素をXNUMXつ減らす操作であるため、配列内のすべての要素を配列内に存在する最小要素に変換する必要があることを直感的に理解できます(減らす必要がないため、さらに)。

等しい配列要素への最小移動の実装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 =配列のサイズ。 配列全体をXNUMX回トラバースします。

スペースの複雑さ 

O(1)、配列で一定のメモリ空間を使用するため。