MinimumMovesToEqualArrayElements [source code]
public class MinimumMovesToEqualArrayElements {
public int minMoves(int[] nums) {
int min = Integer.MAX_VALUE;
for (int i : nums) if (i < min) min = i;
int res = 0;
for (int i : nums) res += i - min;
return res;
}
public int bruteForce(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;
}
public static void main(String[] args) {
MinimumMovesToEqualArrayElements tester = new MinimumMovesToEqualArrayElements();
int[] input1 = {1,2,3};//3
assert tester.minMoves(input1) == 3 : "fail 1";
int[] input2 = {1,2,3,4};//6
assert tester.minMoves(input2) == 6 : "fail 2";
int[] input3 = {3,3,3,1};//6
assert tester.minMoves(input3) == 6 : "fail 3";
int[] input4 = {1,2,3,1};//3
assert tester.minMoves(input4) == 3 : "fail 4";
int[] input5 = {1,1,3,1};//2
assert tester.minMoves(input5) == 2 : "fail 5";
System.out.println(tester.minMoves(input3));
}
}
这个问题最后是完全没有思路的; Math 问题就是这样, 会就会, 不会就一点办法都没有. 这个题目明显是一个 optimization 的问题, 我们知道的可以用的不涉及 backtrack 的 optimization 问题的算法也就有 DP 了; 不过还是没有想到怎么用 DP 来做这个问题;
这个答案是看了 discussion 之后写的, 9ms, 99%;
这个是作者的解释:
Adding 1 to n - 1 elements is the same as subtracting 1 from one element, w.r.t goal of making the elements in the array equal.
So, best way to do this is make all the elements in the array equal to the min element.
sum(array) - n * minimum
底下还有用加法思路来做的(也就是直接 translate 这个公式), 不过那种写法有可能会 overflow, 很麻烦;
这个思路还是很聪明的;
另外, 纯粹从做数学题目的角度来说, 你看到这里 operation 的定义, increment n-1个element, 这个应该是能够刺激到你用 complement 的思路来思考问题的;
虽然解释了一大堆, 笔记也写了很多, 其实这个减法算法的核心思路还是不是特别理解, 暂时先摆一摆了;
当然如果是强行想要理解的话, 可以这样理解, 我们稍微改动一下 operation 的定义: increment n - 1, then decrement all n; 这样一个改动对整个算法的结果是完全没有影响的, 因为我们关系的只是 difference. 不过这样改动了之后确实可以理解为什么可以用减法来理解这个问题;
当然, 当理解了减法之后, 就要记住一个点, 你只能用减法! 因为我们已经把所有的n-1加法都转化成了减法, 所以现在唯一允许的操作就是减法了. 然后你减到什么程度能够相等呢? 当然是 min, 而且其他n-1个element 全都减到 min 为止, 正好就是minimum number of moves;
另外一个比较直白的思路放在 ver2里面了;
discussion 里面有一个人认为用 DP 可以做:
Actually, this problem could be solved by dynamic programming:
sort(nums)
let s = move(nums, 0:k)
then move(nums, 0:k+1) = s + abs(nums[k+1] - nums[k])
return sum(s)
In the end, you will find that this could written as sum(nums) - N * min;
这个思路其实是不正确的, k+1的结果未必比 k 的大.
不过这个思路或许是一个启发, 我还是感觉这个问题可以用 DP 来做.
TODO: 设计一个 DP 的算法;
下面的是 editorial 答案:
Approach #1 Brute Force [Time Limit Exceeded]
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;
}
}
Approach #2 Better Brute Force[Time Limit Exceeded]
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;
}
}
int diff = nums[max] - nums[min];
if (diff == 0) {
break;
}
count += diff;
for (int i = 0; i < nums.length; i++) {
if (i != max) {
nums[i] = nums[i] + diff;
}
}
}
return count;
}
}
这个算法开始就有点不好理解了, 这里作者给出的说法是in each iteration two elements are equalized; 这样确实可以理解, 这个算法肯定可以 halting, 但是这个并不能解释为什么这样算出来的是 min, 因为看起来这个做法其实是有好多次类似越界的操作;
Approach #3 Using Sorting [Accepted]
public class Solution {
public int minMoves(int[] nums) {
Arrays.sort(nums);
int count = 0;
for (int i = nums.length - 1; i > 0; i--) {
count += nums[i] - nums[0];
}
return count;
}
}
这个自己看 editorial, 他这个算法其实还是很聪明的, 解释的也很详细;
不过感觉他介绍的这个, 跟上面第二个算法类似, 都是类似已经提前知道 imperative 了, 知道怎么做了, 比如知道了每次把 min 增加到跟 max 相等就行了; 中间的证明过程其实是没有提供的;
看完了他的解释之后, 整个动态图其实脑子里是非常清晰的, 感觉这个解应该是我自己能够想到的, 而且这个解法本身其实并不怎么依赖事先知道应该increment excpet max这样的东西, 就是一个很纯粹的算法题的思路了;
Approach #4 Using DP [Accepted]
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;
}
}
这个算法是一个特定版本的 DP 解法; 之前我考虑 DP 的时候, 认为 DP 不可行一个原因是在 k 到k+1的过程中, 你无法保证最后的 value 是怎么变化的; 他这里有一个办法, 先 sort 一遍. 这样按照前面的 DP 的思路就可以适用了;
这里也教会了一个思路, 很多问题, sorted 之后确实好解很多. 虽然很多时候 sorting 之后的内容甚至都不占大头, 但是 nlogn 的速度至少比暴力要好; 不要认为先 sort 再做的思路就是没有意义, 很多时候这个结果已经足够好了;
Approach #5 Using Math[Accepted]
public class Solution {
public int minMoves(int[] nums) {
int moves = 0, min = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; i++) {
moves += nums[i];
min = Math.min(min, nums[i]);
}
return moves - min * nums.length;
}
}
从他这里的几个算法里面得到一个思路: 我自己写 ver2的时候, 就有一个地方引起了我的注意, 就是每一个 iteration 我们都要找一次min/max, 这个就很不对劲, 因为按理说哪有算法这么麻烦的. 这里就应该本能想到一个问题, 如果你要时刻对 changing的最值保持 tracking, 那么最好的解决办法就是干脆 sort.
另外一个值得注意的地方, 在判断 equalized 的问题上, 他这里的做法是判断max == min, 我自己写 ver2的时候用的方法是求和什么的. 结果我自己的方法在 input3上面就是死循环, 但是他这个就可以成功. 感觉这个有点像写prolog 的时候的先 sublist 还是后 sublist 的问题差不多;
Problem Description
Given a non-empty integer array of size n, find the minimum number of moves required to make all array elements equal, where a move is incrementing n - 1 elements by 1.
Example:
Input:
[1,2,3]
Output:
3
Explanation:
Only three moves are needed (remember each move increments two elements):
[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]
Difficulty:Easy
Category:Algorithms
Acceptance:46.92%
Contributor: amehrotra2610
Companines
Indeed Coursera
Related Topics
math
Similar question
Minimum Moves to Equal Array Elements II