题目链接:https://leetcode.cn/problems/minimum-cost-to-move-chips-to-the-same-position/
思路
直接想法
这题要求得到移动到同一格子的最小成本,跳两格的成本是0,跳一格的成本是1,所以我们需要尽量跳两格,发现刚好可以分成下标奇偶两列的棋子,可以把奇偶两列的棋子都移动到相邻的点上(移动到1和2上),此时我们只需要对比移动那块的棋子成本最低即可
算法
- 遍历棋子下标 position 数组
。判断元素的奇偶性,把奇数下标记录在odd 元素里
- 对比奇数格子上的棋子和偶数格子上的棋子的数量,返回两者最小值 即可
代码示例
func minCostToMoveChips(position []int) int { odd := 0 for _, v := range position { if v & 1 == 1{ odd++ } } //len(position) - odd表示偶数格子的数量 if odd > len(position) - odd { return len(position) - odd } return odd }
复杂度分析
- 时间复杂度:O(n) 其中n表示数组长度,遍历数组需要花费O(n)的时间
- 空间复杂度:O(1) 没有申请额外空间