本文共 1261 字,大约阅读时间需要 4 分钟。
题目:
Given a non-empty integer array, find the minimum number of moves required to make all array elements equal, where a move is incrementing a selected element by 1 or decrementing a selected element by 1.
You may assume the array’s length is at most 10,000. Example:Input: [1,2,3]Output: 2Explanation: Only two moves are needed (remember each move increments or decrements one element):[1,2,3] => [2,2,3] => [2,2,2]
解释:
这系列的第一题:,其实给n-1
个数字加1
,效果等同于给那个未被选中的数字减1
,所以题目转换成将所有值都转换为最小值所需要的步数。 这道题目是选择一个元素+1或者选择一个元素-1 如果只能-1,则全部往最小值走 如果只能+1,则全部往最大值走 如果能+1也能-1,则全部往中间走 首先给数组排序,那么我们最终需要变成的相等的数字就是中间的数,如果数组有奇数个,那么就是最中间的那个数字;如果是偶数个,那么就是中间两个数的区间中的任意一个数字。 而两端的数字变成中间的一个数字需要的步数实际上就是两端数字的距离(设两端是A
和B
,则需要走的步数=(B-C)+(C-A)
==B-A
),我们就两对两对的累加它们的差值就可以了。 ~
是取反的意思,但是~0==-1
~1==-2
nums[~i]
nums[i]
表示取nums
中对称的元素。 python代码: class Solution(object): def minMoves2(self, nums): """ :type nums: List[int] :rtype: int """ nums.sort() return sum([nums[~i]-nums[i] for i in range(len(nums)/2)])
c++中如何取对称元素。
class Solution { public: int minMoves2(vector & nums) { int n=nums.size(); sort(nums.begin(),nums.end()); int result=0; for (int i=0;i
总结:
~
按位取反运算符:对数据的每个二进制位取反,即把1变为0,把0变为1 。~x
类似于 -x-1
转载地址:http://twmcn.baihongyu.com/