有趣的数学推导题目-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
目录
打赏
0
0
0
0
88
分享
相关文章
|
9月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
99 1
【LeetCode 热题100】347:前 K 个高频元素(详细解析)(Go语言版)
这篇文章详细解析了力扣热题 347——前 K 个高频元素的三种解法:哈希表+小顶堆、哈希表+快速排序和哈希表+桶排序。每种方法都附有清晰的思路讲解和 Go 语言代码实现。小顶堆方法时间复杂度为 O(n log k),适合处理大规模数据;快速排序方法时间复杂度为 O(n log n),适用于数据量较小的场景;桶排序方法在特定条件下能达到线性时间复杂度 O(n)。文章通过对比分析,帮助读者根据实际需求选择最优解法,并提供了完整的代码示例,是一篇非常实用的算法学习资料。
252 90
|
1月前
|
Go
【LeetCode 热题100】DP 实战进阶:最长递增子序列、乘积最大子数组、分割等和子集(力扣300 / 152/ 416 )(Go语言版)
本文深入解析三道经典的动态规划问题:**最长递增子序列(LIS)**、**乘积最大子数组** 和 **分割等和子集**。 - **300. LIS** 通过 `dp[i]` 表示以第 `i` 个元素结尾的最长递增子序列长度,支持 O(n²) 动态规划与 O(n log n) 的二分优化。 - **152. 乘积最大子数组** 利用正负数特性,同时维护最大值与最小值的状态转移方程。 - **416. 分割等和子集** 转化为 0-1 背包问题,通过布尔型 DP 实现子集和判断。 总结对比了三题的状态定义与解法技巧,并延伸至相关变种问题,助你掌握动态规划的核心思想与灵活应用!
81 1
|
9月前
【LeetCode 27】347.前k个高频元素
【LeetCode 27】347.前k个高频元素
92 0
|
9月前
|
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
95 0
|
9月前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
65 4
【C语言】LeetCode(力扣)上经典题目
【C语言】LeetCode(力扣)上经典题目
169 1
|
9月前
|
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
75 0
Leetcode第三十三题(搜索旋转排序数组)
LeetCode第83题删除排序链表中的重复元素
文章介绍了LeetCode第83题"删除排序链表中的重复元素"的解法,使用双指针技术在原链表上原地删除重复元素,提供了一种时间和空间效率都较高的解决方案。
LeetCode第83题删除排序链表中的重复元素
|
9月前
|
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
155 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问