Halo

A magic place for coding

0%

LeetCode 解题报告(380) -- 462. Minimum Moves to Equal Array Elements II

Problem

Given an integer array nums of size n, return the minimum number of moves required to make all array elements equal.

In one move, you can increment or decrement an element of the array by 1.

Test cases are designed so that the answer will fit in a 32-bit integer.

Example 1:

1
2
3
4
5
Input: nums = [1,2,3]
Output: 2
Explanation:
Only two moves are needed (remember each move increments or decrements one element):
[1,2,3] => [2,2,3] => [2,2,2]

Example 2:

1
2
Input: nums = [1,10,2,9]
Output: 16

Constraints:

  • n == nums.length
  • 1 <= nums.length <= 105
  • -109 <= nums [i] <= 109

Analysis

   题目给出一个数组,每次操作只能对一个数 + 1 或 - 1,问最少多少次操作后,能使得数组中所有的元素相等。

   给出两个数,我们要求把这两个数变成相同的数,目标值肯定是在中间,而且中间任意一个数作为目标值,这两个数需要操作的次数都是一样的。例如两个数 1 和 10,如果要都变成 2,1 需要操作 1 次,10 需要操作 8 次,一共 9 次;如果都变成 5,1 需要操作 4 次,10 需要操作 5 次,一共也是 9 次。因此操作次数是两数之差。

   按照这个规律,我们只需要头尾两数相减,一直往中间走,把他们的差都加起来就是操作的数量。


Solution

   无


Code

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
int minMoves2(vector<int>& nums) {
int result = 0, i = 0, j = nums.size () - 1;
sort (nums.begin (), nums.end ());
while (i < j) {
result += (nums [j--] - nums [i++]);
}
return result;
}
};

Summary

   这道题是一道比较简单的数组题,其涉及到的更多是基础数学。这道题目的分享到这里,感谢你的支持!

Welcome to my other publishing channels