给定一个长度为 n 的非空整数数组，找到让数组所有元素相等的最小移动次数。每次移动可以使 n - 1 个元素增加 1。
示例:
输入: [1,2,3] 输出: 3 解释: 只需要3次移动（注意每次移动会增加两个元素的值）： [1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]
自我思考：
观察规律，移动次数是数组内最大值减去最小值，然后生成新数组后继续用最大值减最小值，直到这个差为0，每次的差的和就是移动次数
代码实现如下
1 import java.io.IOException; 2 import java.util.Scanner; 3 4 5 public class MainClass { 6 public static void main(String[] args) throws IOException{ 7 Scanner input = new Scanner(System.in); 8 System.out.println("请输入数组，元素间以逗号隔开："); 9 int[] nums=stringToArray(input.nextLine()); 10 Solution getMoves=new Solution(); 11 int moves=getMoves.minMoves(nums); 12 System.out.println("最少移动次数为："); 13 System.out.println(moves); 14 } 15 public static int[] stringToArray(String str){ 16 String[] strArr= str.split(","); 17 int[] arr=new int[strArr.length]; 18 for(int i=0;i<strArr.length;i++){ 19 arr[i]=Integer.parseInt(strArr[i].trim()); 20 } 21 return arr; 22 } 23 } 24 25 class Solution { 26 public int minMoves(int[] nums) { 27 int minMoves=move(nums,0); 28 29 return minMoves; 30 } 31 32 public int[] subMaxMin(int[] nums){ 33 int max=0,min=0; 34 for(int i=1;i<nums.length;i++){ 35 if(nums[max]<nums[i]){ 36 max=i; 37 } 38 if(nums[min]>nums[i]){ 39 min=i; 40 } 41 } 42 int[] maxAndMin={max,min}; 43 return maxAndMin; 44 } 45 46 public int move(int[] nums,int sumMove){ 47 int[] maxAndMin=subMaxMin(nums); 48 int moves=nums[maxAndMin[0]]-nums[maxAndMin[1]]; 49 if(moves!=0){ 50 sumMove+=moves; 51 for(int i=0;i<nums.length;i++){ 52 if(i!=maxAndMin[0]){ 53 nums[i]+=moves; 54 } 55 } 56 return move(nums,sumMove); 57 }else{ 58 return sumMove; 59 } 60 } 61 }
本实现在leetcode提交后，因为超时，被拒，虽然在myeclipes中可以快速运行，但在线调试显示发费时间极高，[1，2，3]花费时间在120ms左右。
百度后发现： 本算法的核心是移动次数是数组内其他元素减去最小值的和，所以。。。。
1 class Solution { 2 public int minMoves(int[] nums) { 3 int sum=0,moves,min=nums[0]; 4 for(int i=0;i<nums.length;i++){ 5 sum+=nums[i]; 6 if(nums[i]<min){ 7 min=nums[i]; 8 } 9 } 10 moves=sum-min*nums.length; 11 return moves; 12 } 13 }
抽自己几个耳刮子才行？！！