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月前
|
程序员 C语言
【C语言】LeetCode(力扣)上经典题目
【C语言】LeetCode(力扣)上经典题目
|
2月前
|
索引
力扣(LeetCode)数据结构练习题(3)------链表
力扣(LeetCode)数据结构练习题(3)------链表
95 0
|
2月前
力扣(LeetCode)数据结构练习题(2)
力扣(LeetCode)数据结构练习题(2)
31 0
|
2月前
|
存储
力扣(LeetCode)数据结构练习题
力扣(LeetCode)数据结构练习题
56 0
|
3月前
|
Go
Golang语言之数组(array)快速入门篇
这篇文章是关于Go语言中数组的详细教程,包括数组的定义、遍历、注意事项、多维数组的使用以及相关练习题。
43 5
|
3月前
|
Go
Golang语言之管道channel快速入门篇
这篇文章是关于Go语言中管道(channel)的快速入门教程,涵盖了管道的基本使用、有缓冲和无缓冲管道的区别、管道的关闭、遍历、协程和管道的协同工作、单向通道的使用以及select多路复用的详细案例和解释。
140 4
Golang语言之管道channel快速入门篇
|
3月前
|
Go
Golang语言文件操作快速入门篇
这篇文章是关于Go语言文件操作快速入门的教程,涵盖了文件的读取、写入、复制操作以及使用标准库中的ioutil、bufio、os等包进行文件操作的详细案例。
71 4
Golang语言文件操作快速入门篇
|
3月前
|
Go
Golang语言之gRPC程序设计示例
这篇文章是关于Golang语言使用gRPC进行程序设计的详细教程,涵盖了RPC协议的介绍、gRPC环境的搭建、Protocol Buffers的使用、gRPC服务的编写和通信示例。
112 3
Golang语言之gRPC程序设计示例
|
3月前
|
安全 Go
Golang语言goroutine协程并发安全及锁机制
这篇文章是关于Go语言中多协程操作同一数据问题、互斥锁Mutex和读写互斥锁RWMutex的详细介绍及使用案例,涵盖了如何使用这些同步原语来解决并发访问共享资源时的数据安全问题。
100 4
|
3月前
|
Go
Golang语言错误处理机制
这篇文章是关于Golang语言错误处理机制的教程,介绍了使用defer结合recover捕获错误、基于errors.New自定义错误以及使用panic抛出自定义错误的方法。
55 3