[leetcode] 1551. Minimum Operations to Make Array Equal

[leetcode] 1551. Minimum Operations to Make Array Equal

Description

You have an array arr of length n where arr[i] = (2 * i) + 1 for all valid values of i (i.e. 0 <= i < n).

In one operation, you can select two indices x and y where 0 <= x, y < n and subtract 1 from arr[x] and add 1 to arr[y] (i.e. perform arr[x] -=1 and arr[y] += 1). The goal is to make all the elements of the array equal. It is guaranteed that all the elements of the array can be made equal using some operations.

Given an integer n, the length of the array. Return the minimum number of operations needed to make all the elements of arr equal.

Example 1:

Input: n = 3Output: 2Explanation: arr = [1, 3, 5]First operation choose x = 2 and y = 0, this leads arr to be [2, 3, 4]In the second operation choose x = 2 and y = 0 again, thus arr = [3, 3, 3].

Example 2:

Input: n = 6Output: 9

Constraints:

1 <= n <= 10^4

分析

题目的意思是：给定数字n，代表数组的长度，数组中的值为位置索引的两倍+1，求最小的操作步骤（两个位置同时执行+1，-1操作）使得数组中的所有的数相等.这道题要找规律，其中数组每个位置最终变成的数就为n，因为n就是求和后的平均值，然后看每个位置变成平均数n需要的操作数，然后求和就行了，因为操作是对称的，所以只需要考虑前半部分就行了。 比如：

[1,3,5,7,9]1 9，3 7，5 分别组成一组进行操作，然后操作数求和就行了

我看见有人总结的规律更精辟：((n + 1) // 2) * (n // 2) 膜拜一下

代码

class Solution: def minOperations(self, n: int) -> int: res=0 for i in range(n//2): t=2*i+1 res+=abs(n-t) return res

参考文献

​​Simple Solution by Python 3​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。