龙空技术网

LeetCode基础算法题第95篇:通过总结规律解题

吾是我师 944

前言:

今天同学们对“leetcode算法题解代码”可能比较关注,你们都想要分析一些“leetcode算法题解代码”的相关内容。那么小编同时在网上汇集了一些关于“leetcode算法题解代码””的相关知识,希望姐妹们能喜欢,兄弟们一起来了解一下吧!

技术提高是一个循序渐进的过程,所以我讲的leetcode算法题从最简单的level开始写的,然后到中级难度,最后到hard难度全部完。

目前我选择C语言,Python和Java作为实现语言,因为这三种语言还是比较典型的。由于篇幅和精力有限,其他语言的实现有兴趣的朋友请自己尝试。

初级难度说的差不多的时候,我打算再加点其他内容,我可能会从操作系统到协议栈,从分布式聊到大数据框架,从大数据聊到人工智能,... ...。

如果有任何问题可以在文章后评论或者私信给我。

我会持续分享下去,敬请您的关注。

LeetCode 453. 最小移动次数使数组元素相等(Minimum Moves to Equal Array Elements)

问题描述:

给定一个长度为 n 的非空整数数组,找到让数组所有元素相等的最小移动次数。每次移动可以使 n - 1 个元素增加 1。

示例:C语言实现:

首先要实现这个目的,你需要做到:

每次移动,最大的那个数都不能动,即除了最大数之外其他的数都加1,注意我说的是每次,也就是说,所谓的最大数每次移动后可能都会发生变化。

这个问题是有规律的,如果你能发现,就能很容易写出算法。

为了总结这个规律,我下面以两个例子来说明:

如上图,第一个示例假设输入数组是[2,3,4],通过移动最终变成数组[5,5,5],最小的元素是2,在整个过程中始终在累加,从2变到5变化了3次。而元素3最后一次没有动,所以整个过程中变化了2次,同理4到5变化了1次,总的变化次数是3,它和最小元素3的变化次数一样,同时又是除了最小元素外其他元素的变化次数的和。这是第一个规律。

请注意看我下面列出来的表达式,总的变化次数又等于每个元素和最小元素的差的和,换句话说就是整个列表的和减去n个最小元素,其中n是数组的长度。

第二个示例[2,2,3,5]可以得出同样的结果。

因此我们就可以得出如下的代码:

提醒一下,sum的必须是long类型,因为sum记录的是数字元素的和,这个值可能会超出int类型的取值范围。

python语言的实现:

python的实现和C语言实现基本一致

代码如下:

Java语言的实现:

Java的实现和C语言的实现基本一致。

代码如下:

标签: #leetcode算法题解代码