首页 > 代码库 > leetcode 453

leetcode 453

2024-08-24 07:49:13   212人阅读

题目描述：

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]

 

题目解析：

题目很简单，我的理解就是找到最大的元素，用最大元素减去每个元素，将所有的差相加就得到了最后的moves，这就是我的第一个版本的代码，很可惜运行时间超了：

bool my_compare(int first_arg, int second_arg)
{
    return first_arg >= second_arg; 
}

class Solution {
public:
    int minMoves(vector<int>& nums) {
        if(nums.size() == 0)
            return 0;
        sort(nums.begin(), nums.end(), my_compare);
        int moves = 0, biggest_num = nums[0];
        for (auto n: nums)
            moves += (biggest_num - n);
        return moves;
    }
};

 

 

于是有了第二个版本，这个解法中使用一个局部最大值，不是全局最大值，每次更新局部最大值时也更新moves，代码如下：

class Solution {
public:
    int minMoves(vector<int>& nums) {
        if(nums.size() == 0)
            return 0;
        int moves = 0, max_temp = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            if(max_temp < nums[i])
            {
                moves += i * (nums[i] - max_temp);
                max_temp = nums[i];
            }
            else
                moves += (max_temp - nums[i]);
        }
        return moves;
    }
};

很可惜这个版本的代码还是有bug，会导致溢出……

 

以上两个版本的代码的问题都是自己理解有问题，这太傻了！！！！每次移动要求同时将n-1个元素加1，自己看错了……这个教训很好。但是明白题目的含义之后，我好像又不会做了，真是尴尬。

看了其他人的博客发现，原来这个题一行代码就搞定了（python），呵呵呵！原博的分析如下：

原博地址：http://blog.csdn.net/buptzhengchaojie/article/details/53065675

给数组中的n-1个元素加1的操作等价于数组中“不加1的那个元素“减去1，然后数组中的所有元素都加1。我们知道，给所有的元素都加1并不能改变原数组中的数之间的差值。所以这题就转化为求最少的减1操作。而要使数组中的元素全部相等，又要使用减法。那么最少的次数就是让这些元素全部都等于数组中最小的数。所以得到的结果就是sum（所有元素和）-n*数组中最小元素。

 

而且这时又遇到一个问题，c++的api用的不熟，不知道c++有没有min这个api，实验了一下，发现果然没有这个api，就这样很开心地写起来for循环，c++代码如下：

class Solution {
public:
    int minMoves(vector<int>& nums) {
        if(nums.size() == 0)
            return 0;
        int sum = 0, min_n = nums[0];
        for (auto n: nums)
        {
            sum += n;
            if(n < min_n)
                min_n = n;
        }
        return sum - min_n * nums.size();
    }
};

 

python版的代码一行完事：

class Solution(object):
    def minMoves(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return sum(nums) - min(nums) * len(nums)

 

总之做了一回冤大头，题目看错，也是眼瞎！明天再刷一遍吧。

 

leetcode 453






























        

            
                
                  
                
                

                    联系

                    我们