最小移动到相等的数组元素Leetcode解决方案  


难度级别 易得奖学金
经常问 亚马逊 Apple Coursera 事实集 的确 摩根大通 数学作品 微软 Swiggy
算法 编码 吊桥 访谈 面试准备 力码 力码解决方案 数学

问题陈述  

在这个问题上,我们得到了一个 排列 整数同样,我们被允许在此数组上执行一组特定的操作。 在一个操作中,我们可以将数组中的“ 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解决方案的复杂性分析

时间复杂度

上),N =数组的大小。 我们遍历整个数组一次。

参见
单调数组LeetCode解决方案

空间复杂度 

O(1),因为我们在数组中使用恒定的内存空间。

1