前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【算法千题案例】⚡️每日LeetCode打卡⚡️——56.最小操作次数使数组元素相等

【算法千题案例】⚡️每日LeetCode打卡⚡️——56.最小操作次数使数组元素相等

作者头像
呆呆敲代码的小Y
发布2021-10-20 16:09:41
3110
发布2021-10-20 16:09:41
举报

请添加图片描述
请添加图片描述

????前言

???? 算法题 ????

  • ???? 每天打卡一道算法题,既是一个学习过程,又是一个分享的过程????
  • ???? 提示:本专栏解题 编程语言一律使用 C# 和 Java 两种进行解题
  • ???? 要保持一个每天都在学习的状态,让我们一起努力成为算法大神吧????!
  • ???? 今天是力扣算法题持续打卡第56天????!

???? 算法题 ????


????原题样例:找到所有数组中消失的数字

给你一个长度为n 的整数数组,每次操作将会使 n - 1个元素增加1。返回让数组所有元素相等的最小操作次数。

示例:

代码语言:javascript
复制
输入:nums = [1,2,3]
输出:3
解释:
只需要3次操作(注意每次操作会增加两个元素的值):
[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]

示例 2:

代码语言:javascript
复制
输入:nums = [1,1,1]
输出:0

提示:

  • n == nums.length
  • 1 <= nums.length <= 105
  • -109 <= nums[i] <= 109 答案保证符合 32-bit 整数

????C#方法:排序

使用return nums.Sum() - nums.Min() * nums.Length;就可以搞定,但是Sum会溢出

所以修改为以下代码,遍历一遍即可!

代码:

代码语言:javascript
复制
public class Solution {
    public int MinMoves(int[] nums) {
             int iSum = nums.Min() * nums.Length * -1;
            foreach (var num in nums)
            {
                iSum += num;
            }
            return iSum;
    }
}

执行结果

代码语言:javascript
复制
通过
执行用时:156 ms,在所有 C# 提交中击败了53.85%用户
内存消耗:48.1 MB,在所有 C# 提交中击败了23.08%的用户

????Java 方法一:暴力法 【超时】

思路解析

  • 首先,我们知道,为了在最小移动内使所有元素相等,我们需要在数组的最大元素之外的所有元素中执行增加。
  • 因此,在暴力法中,我们扫描整个数组以查找最大值和最小元素。
  • 此后,我们将 111 添加到除最大元素之外的所有元素,并增加移动数的计数。
  • 同样,我们重复相同的过程,直到最大元素和最小元素彼此相等。

代码:

代码语言:javascript
复制
public class Solution {
    public int minMoves(int[] nums) {
        int min = 0, max = nums.length - 1, count = 0;
        while (true) {
            for (int i = 0; i < nums.length; i++) {
                if (nums[max] < nums[i]) {
                    max = i;
                }
                if (nums[min] > nums[i]) {
                    min = i;
                }
            }
            if (nums[max] == nums[min]) {
                break;
            }
            for (int i = 0; i < nums.length; i++) {
                if (i != max) {
                    nums[i]++;
                }
            }
            count++;
        }
        return count;
    }
}

执行结果

代码语言:javascript
复制
超时

复杂度分析

代码语言:javascript
复制
时间复杂度:O( n^2 k ),其中 n 为数组长度,k 为最大值和最小值的差。
空间复杂度:O( 1) 

????Java 方法二:动态规划

思路解析

在这里插入图片描述
在这里插入图片描述

代码:

代码语言:javascript
复制
public class Solution {
    public int minMoves(int[] nums) {
        Arrays.sort(nums);
        int moves = 0;
        for (int i = 1; i < nums.length; i++) {
            int diff = (moves + nums[i]) - nums[i - 1];
            nums[i] += moves;
            moves += diff;
        }
        return moves;
    }
}

执行结果

代码语言:javascript
复制
通过
执行用时:13 ms,在所有 Java  提交中击败了20.05%的用户
内存消耗:38.6 MB,在所有 Java 提交中击败了92.21%的用户

复杂度分析

代码语言:javascript
复制
时间复杂度:O( nlog(n) )
空间复杂度:O( 1) 

????总结

  • 今天是力扣算法题打卡的第五十六天!
  • 文章采用 C#Java 两种编程语言进行解题
  • 一些方法也是参考力扣大神写的,也是边学习边分享,再次感谢算法大佬们
  • 那今天的算法题分享到此结束啦,明天再见!
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2021-10-18 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • ????前言
  • ????原题样例:找到所有数组中消失的数字
    • ????C#方法:排序
      • ????Java 方法一:暴力法 【超时】
        • ????Java 方法二:动态规划
        • ????总结
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档