golang力扣leetcode 462.最少移动次数使数组元素相等II

简介: golang力扣leetcode 462.最少移动次数使数组元素相等II

462.最少移动次数使数组元素相等II

462.最少移动次数使数组元素相等II

题解

题目:让所有数组元素变成相等的数字,一次只能加一或减一,问需要几次

思路:

  1. 需要找到一个数字,计算元素到该数字的距离即可
  2. 如何求这个数字呢?

设x在区间[a0,a1,a2,a3,a4,…,an]外,对于a0和an来说,ans=a0-x + an -x

设x在区间[a0,a1,a2,a3,a4,…,an]内,对于a0和an来说,ans=an-a0

那么肯定在区间内,比区间外的步数小。

同理不断扩大a0,缩小an,最终这个x就是数组排序后的中位数

代码

func minMoves2(nums []int) int {
  sort.Ints(nums)
  l, r := 0, len(nums)-1
  ans := 0
  for l < r {
    ans += nums[r] - nums[l]
    l++
    r--
  }
  return ans
}
func minMoves2(nums []int) int {
  sort.Ints(nums)
  mid := 0
  if len(nums)%2 == 0 {
    mid = (nums[len(nums)/2-1] + nums[len(nums)/2]) / 2
  } else {
    mid = nums[len(nums)/2]
  }
  ans := 0
  for _, v := range nums {
    ans += abs(v - mid)
  }
  return ans
}
func abs(i int) int {
  if i > 0 {
    return i
  }
  return -i
}
目录
相关文章
|
2月前
|
算法
LeetCode第53题最大子数组和
LeetCode第53题"最大子数组和"的解题方法,利用动态规划思想,通过一次遍历数组,维护到当前元素为止的最大子数组和,有效避免了复杂度更高的暴力解法。
LeetCode第53题最大子数组和
LeetCode------找到所有数组中消失的数字(6)【数组】
这篇文章介绍了LeetCode上的"找到所有数组中消失的数字"问题,提供了一种解法,通过两次遍历来找出所有未在数组中出现的数字:第一次遍历将数组中的每个数字对应位置的值增加数组长度,第二次遍历找出所有未被增加的数字,即缺失的数字。
|
2月前
|
存储 算法
LeetCode第83题删除排序链表中的重复元素
文章介绍了LeetCode第83题"删除排序链表中的重复元素"的解法,使用双指针技术在原链表上原地删除重复元素,提供了一种时间和空间效率都较高的解决方案。
LeetCode第83题删除排序链表中的重复元素
|
2月前
|
算法
LeetCode第81题搜索旋转排序数组 II
文章讲解了LeetCode第81题"搜索旋转排序数组 II"的解法,通过二分查找算法并加入去重逻辑来解决在旋转且含有重复元素的数组中搜索特定值的问题。
LeetCode第81题搜索旋转排序数组 II
|
1月前
|
Go
Golang语言之数组(array)快速入门篇
这篇文章是关于Go语言中数组的详细教程,包括数组的定义、遍历、注意事项、多维数组的使用以及相关练习题。
21 5
|
2月前
|
算法 索引
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
这篇文章介绍了LeetCode第34题"在排序数组中查找元素的第一个和最后一个位置"的解题方法,通过使用双指针法从数组两端向中间同时查找目标值,有效地找到了目标值的首次和最后一次出现的索引位置。
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
|
2月前
|
算法
LeetCode第33题搜索旋转排序数组
这篇文章介绍了LeetCode第33题"搜索旋转排序数组"的解题方法,通过使用二分查找法并根据数组的有序性质调整搜索范围,实现了时间复杂度为O(log n)的高效搜索算法。
LeetCode第33题搜索旋转排序数组
|
2月前
|
算法
LeetCode第27题移除元素
这篇文章介绍了LeetCode第27题"移除元素"的解题方法,通过使用双指针技巧,有效移除数组中特定值的元素并返回新数组的长度。
|
2月前
|
监控 Serverless Go
Golang 开发函数计算问题之Go 语言中切片扩容时需要拷贝原数组中的数据如何解决
Golang 开发函数计算问题之Go 语言中切片扩容时需要拷贝原数组中的数据如何解决
|
5天前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行