跳至主要內容

1217. 玩筹码

ITCharge大约 2 分钟

1217. 玩筹码open in new window

  • 标签:贪心、数组、数学
  • 难度:简单

题目链接

题目大意

描述:给定一个数组 positionposition 代表 nn 个筹码的位置,其中 position[i]position[i] 代表第 ii 个筹码的位置。现在需要把所有筹码移到同一个位置。在一步中,我们可以将第 ii 个芯片的位置从 position[i]position[i] 改变为:

  • position[i]+2position[i] + 2position[i]2position[i] - 2,此时 cost=0cost = 0
  • position[i]+1position[i] + 1position[i]1position[i] - 1,此时 cost=1cost = 1

即移动偶数位长度的代价为 00,移动奇数位长度的代价为 11

要求:返回将所有筹码移动到同一位置上所需要的 最小代价 。

说明

  • 1chips.length1001 \le chips.length \le 100
  • 1chips[i]1091 \le chips[i] \le 10^9

示例

  • 示例 1:
输入:position = [2,2,2,3,3]
输出:2
解释:我们可以把位置3的两个芯片移到位置 2。每一步的成本为 1。总成本 = 2

解题思路

思路 1:贪心算法

题目中移动偶数位长度是不需要代价的,所以奇数位移动到奇数位不需要代价,偶数位移动到偶数位也不需要代价。

则我们可以想将所有偶数位都移动到下标为 00 的位置,奇数位都移动到下标为 11 的位置。

这样,所有的奇数位、偶数位上的人都到相同或相邻位置了。

我们只需要统计一下奇数位和偶数位的数字个数。将少的数移动到多的数上边就是最小代价。

则这道题就可以通过以下步骤求解:

  • 遍历数组,统计数组中奇数个数和偶数个数。
  • 返回奇数个数和偶数个数中较小的数即为答案。

思路 1:贪心算法代码

class Solution:
    def minCostToMoveChips(self, position: List[int]) -> int:
        odd, even = 0, 0
        for p in position:
            if p & 1:
                odd += 1
            else:
                even += 1
        return min(odd, even)

思路 1:复杂度分析

  • 时间复杂度O(n)O(n),其中 nn 为数组 poitionpoition 的长度。
  • 空间复杂度O(1)O(1)