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试题
【数组相关面试题】LeetCode试题
|
2月前
|
算法 Java
[Java·算法·简单] LeetCode 27. 移除元素 详细解读
[Java·算法·简单] LeetCode 27. 移除元素 详细解读
23 1
|
2月前
|
算法 C语言
【C语言】Leetcode 27.移除元素
【C语言】Leetcode 27.移除元素
21 0
【C语言】Leetcode 27.移除元素
【移除链表元素】LeetCode第203题讲解
【移除链表元素】LeetCode第203题讲解
|
2月前
|
算法
LeetCode[题解] 1261. 在受污染的二叉树中查找元素
LeetCode[题解] 1261. 在受污染的二叉树中查找元素
16 1
|
20天前
【Leetcode】两数之和,给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。
【Leetcode】两数之和,给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。
|
6天前
[leetcode~dfs]1261. 在受污染的二叉树中查找元素
[leetcode~dfs]1261. 在受污染的二叉树中查找元素
[leetcode~dfs]1261. 在受污染的二叉树中查找元素
|
12天前
|
算法
代码随想录算法训练营第五十七天 | LeetCode 739. 每日温度、496. 下一个更大元素 I
代码随想录算法训练营第五十七天 | LeetCode 739. 每日温度、496. 下一个更大元素 I
15 3
|
15天前
【力扣】238. 除自身以外数组的乘积
【力扣】238. 除自身以外数组的乘积
|
15天前
|
算法
【力扣】169. 多数元素
【力扣】169. 多数元素