贪心题目：玩筹码

文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题玩筹码出处1217. 玩筹码难度3 级题目描述要求有n \texttt{n}n个筹码第i \texttt{i}i个筹码的位置是position[i] \texttt{position[i]}position[i]。需要把所有筹码移到同一个位置。在一步中可以将第i \texttt{i}i个筹码的位置从position[i] \texttt{position[i]}position[i]移动到以下位置并需要相应的代价position[i] 2 \texttt{position[i]} \texttt{2}position[i]2或position[i] − 2 \texttt{position[i]} - \texttt{2}position[i]−2代价为0 \texttt{0}0。position[i] 1 \texttt{position[i]} \texttt{1}position[i]1或position[i] − 1 \texttt{position[i]} - \texttt{1}position[i]−1代价为1 \texttt{1}1。返回将所有筹码移动到同一位置上所需要的最小代价。示例示例 1输入position [1,2,3] \texttt{position [1,2,3]}position [1,2,3]输出1 \texttt{1}1解释第一步将位置3 \texttt{3}3的筹码移动到位置1 \texttt{1}1成本是0 \texttt{0}0。第二步将位置2 \texttt{2}2的筹码移动到位置1 \texttt{1}1成本是1 \texttt{1}1。总成本是1 \texttt{1}1。示例 2输入position [2,2,2,3,3] \texttt{position [2,2,2,3,3]}position [2,2,2,3,3]输出2 \texttt{2}2解释可以把位置3 \texttt{3}3的两个筹码移到位置2 \texttt{2}2。每一步的成本是1 \texttt{1}1。总成本是2 \texttt{2}2。示例 3输入position [1,1000000000] \texttt{position [1,1000000000]}position [1,1000000000]输出1 \texttt{1}1数据范围1 ≤ position.length ≤ 100 \texttt{1} \le \texttt{position.length} \le \texttt{100}1≤position.length≤1001 ≤ position[i] ≤ 10 9 \texttt{1} \le \texttt{position[i]} \le \texttt{10}^\texttt{9}1≤position[i]≤109解法思路和算法根据移动筹码的规则将一个筹码移动到相差2 22的位置需要的代价是0 00将一个筹码移动到相差1 11的位置需要的代价是1 11。由于移动到相差2 22的位置之后筹码所在的位置的奇偶性不变移动到相差1 11的位置之后筹码所在的位置的奇偶性改变因此可以在使用代价0 00的情况下分别将所有位于奇数位置的筹码移动到同一个奇数位置和将所有位于偶数位置的筹码移动到同一个偶数位置且该奇数位置和该偶数位置相邻。将所有筹码移动到相邻的奇数位置和偶数位置之后将所有筹码移动到同一位置上可能有两种情况一是将奇数位置的筹码全部移动到偶数位置偶数位置的筹码不移动二是将偶数位置的筹码全部移动到奇数位置奇数位置的筹码不移动。第一种情况的总代价等于奇数位置的筹码个数第二种情况的总代价等于偶数位置的筹码个数两种情况的总代价中的最小值即为将所有筹码移动到同一位置上所需要的最小代价。特别地如果初始时所有筹码都位于奇数位置或所有筹码都位于偶数位置则可以在使用代价0 00的情况下将所有筹码移动到同一个位置最小代价为0 00。根据上述分析计算将所有筹码移动到同一位置上所需要的最小代价的做法是遍历数组position \textit{position}position分别统计位于奇数位置和位于偶数位置的筹码数其中的较小值即为最小代价。代码classSolution{publicintminCostToMoveChips(int[]position){int[]countsnewint[2];for(intchip:position){counts[chip%2];}returnMath.min(counts[0],counts[1]);}}复杂度分析时间复杂度O ( n ) O(n)O(n)其中n nn是数组position \textit{position}position的长度。需要遍历数组position \textit{position}position一次对于每个元素更新计数的时间是O ( 1 ) O(1)O(1)。空间复杂度O ( 1 ) O(1)O(1)。