Thinking process of solving problems use Java, 37ms


  • 6

    First time, I try to find the max num every time, and +1 to rest num, code like below:

        public int minMoves(int[] nums) {
            return helper(nums, 0);
        }
    
        private int helper(int[] nums, int count) {
            int max = 0;
            int total = 1;
            for (int i = 1; i < nums.length; i++) {
                if (nums[i] > nums[max]) max = i;
                else if (nums[i] == nums[max]) total++;
            }
            if (total == nums.length) return count;
    
            for (int i = 0; i < nums.length; i++) {
                if (i != max) nums[i]++;
            }
            return helper(nums, ++count);
        }
    

    but when the nums is [1, 1, 2147483647], it will be java.lang.StackOverflowError.

    So I try to improve in this way that find the max and min num every time, and +(max - min) to rest num, code like below:

        public int minMoves(int[] nums) {
            return helper(nums, 0);
        }
    
        private int helper(int[] nums, int count) {
            int max = 0, min = 0;
            int total = 1;
            for (int i = 1; i < nums.length; i++) {
                if (nums[i] > nums[max]) max = i;
                else if (nums[i] < nums[min]) min = i;
                else if (nums[i] == nums[max]) total++;
            }
            if (total == nums.length) return count;
    
            int dis = nums[max] - nums[min];
            for (int i = 0; i < nums.length; i++) {
                if (i != max) nums[i] += dis;
            }
            return helper(nums, count + dis);
        }
    

    But when the num length is bigger to 10000, it wil be Time Limit Exceeded.

    Then, I want to implements it by no recursive way and use insert sort every time in order to reduce unnecessary traversal operation. code like below:

        public int minMoves(int[] nums) {
            int res = 0;
            int n = nums.length;
            Arrays.sort(nums);
    
            while (nums[n - 1] != nums[0]) {
                int dis = nums[n - 1] - nums[0];
                for (int i = 0; i < n - 1; i++) {
                    nums[i] += dis;
                }
                res += dis;
    
                //insert sort
                int max = nums[n - 1];
                int i = n - 2;
                while (i >= 0) {
                    if (nums[i] > max) nums[i + 1] = nums[i--];
                    else break;
                }
                nums[i + 1] = max;
            }
    
            return res;
        }
    

    But it still Time Limit Exceeded.

    ============== The final solution is as follows ==============

    The final flash, I though that should we use dynamic programming?

    • [step] is The number of steps arrive at the state of [all equal]
    • [finalNum] is The value of the state of [all equal]

    we can know that

    • step[i] = (step[i-1] + num[i]) - finalNum[i-1] + step[i-1]
    • finalNum[i] = num[i] + step[i-1]
        public int minMoves(int[] nums) {
            Arrays.sort(nums);
    
            int n = nums.length;
            int step = 0;
            int finalNum = nums[0];
    
            for (int i = 1; i < n; i++) {
                int tmp = finalNum;
                finalNum = nums[i] + step;
                if (finalNum == tmp) continue;   //attention!!
                step = finalNum - tmp + step;
            }
    
            return step;
        }
    

  • 0
    M

    @zhangCabbage
    Hello, Thanks for sharing your thinking process.
    Would you mind explaining why the final algotirhmn does find the minimum value of moment needed?
    I am little bit confused with it. Thanks in advance!


  • 0

    @Matthew_Lin the final algorithm´╝čAre you asking why the dp solution need Arrays.sort(nums)? From the before three trying, we can see that we want to handle the smaller num first moment, because comparing to the bigger one, smaller num must need more add 1.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.