有趣的数学推导题目-leetcode462. 最少移动次数使数组元素相等 II

简介: 有趣的数学推导题目-leetcode462. 最少移动次数使数组元素相等 II

给你一个长度为 n 的整数数组 nums ,返回使所有数组元素相等需要的最少移动数。


在一步操作中,你可以使数组中的一个元素加 1 或者减 1 。


示例 1:


输入:nums = [1,2,3]

输出:2

解释:

只需要两步操作(每步操作指南使一个元素加 1 或减 1):

[1,2,3]  =>  [2,2,3]  =>  [2,2,2]

示例 2:


输入:nums = [1,10,2,9]

输出:16


提示:


n == nums.length

1 <= nums.length <= 105

-109 <= nums[i] <= 109

通过次数21,388提交次数34,608


题解:

参考 jam大神的方法,相当于找出规律了

当 数组长度为奇数的时候

【1 , 2 , 3】

res = 2-1 + 3-2 = 3-1 = 2

类似 i-1 + 3-i = 3-1 =2

当时 数组长度为偶数的时候

【1 , 4】

res = i-1 + 4-i = 4-1

因此 可看下面代码


Python代码暴力:

class Solution:
    def minMoves2(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        if n==2: return nums[1]-nums[0]
        if n==1 or n==0: return 0
        ans = 0
        res = 0
        if n%2==0: 
            a = nums[n//2-1]
            b = nums[(n+2)//2-1]
            c = 0
            for i in nums:
                res += abs(a-i)
            for j in nums:
                c += abs(b-j)
            return min(c , res) 
        else: 
            ans = nums[n//2]
            for i in nums:
                res += abs(ans-i)
            return res


数学方法推导的C++代码:

class Solution {
public:
    int minMoves2(vector<int>& nums) {
        sort(nums.begin() , nums.end());
        int left=0 , res=0 , right = nums.size()-1;
        while (left<right){
            res += (nums[right]-nums[left]);
            left++;
            right--;
        }
        return res;
    }
};

 数学方法推导的python代码:

class Solution:
    def minMoves2(self, nums: List[int]) -> int:
        nums.sort()
        res , left , right = 0 , 0 , len(nums)-1
        while left<right:
            res += nums[right]-nums[left]
            left += 1
            right -= 1
        return res
相关文章
|
2月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
36 1
|
2月前
【LeetCode 27】347.前k个高频元素
【LeetCode 27】347.前k个高频元素
34 0
|
2月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
40 0
|
4月前
|
算法
LeetCode第53题最大子数组和
LeetCode第53题"最大子数组和"的解题方法,利用动态规划思想,通过一次遍历数组,维护到当前元素为止的最大子数组和,有效避免了复杂度更高的暴力解法。
LeetCode第53题最大子数组和
|
2月前
|
程序员 C语言
【C语言】LeetCode(力扣)上经典题目
【C语言】LeetCode(力扣)上经典题目
|
2月前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
21 4
|
2月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
19 0
Leetcode第三十三题(搜索旋转排序数组)
|
2月前
|
算法 C++
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
68 0
|
2月前
|
C++
【LeetCode 12】349.两个数组的交集
【LeetCode 12】349.两个数组的交集
17 0
|
2月前
【LeetCode 06】203.移除链表元素
【LeetCode 06】203.移除链表元素
30 0