在x轴上分布着n个石子,用arr数组表示他们的位置,把这些石子移动到1,3,5,7,2n-1或者2,4,6,8,2n
也就是说这些石子移动到从1开始连续的奇数位或从2开始连续的偶数位上,返回最少的移动次数,每次只可以移动1个石子,只能把石子往左或
往右移动1个位置,同一个位置不能有两个石子。
输入[5,4,1],只需把4移动到3,只需一步,
输入[1,6,7,8,9],最优移动方案位把1移动到2,把6移动到4,把7移动到6,把9移动到10,需要5步。
# 代码示例
#方法1:分别创建奇数列表和偶数列表,然后用两个列表分别减arr相同位置的值
class Solution1:
def move_count(self,arr):
arr = sorted(arr)
one = [i for i in range(1, 2 * len(arr), 2)]#奇数列表
two = [i for i in range(2, 2 * len(arr) + 1, 2)]#偶数列表
one_count = 0
two_count = 0
for c in range(len(arr)):
one_count += abs(one[c]-arr[c])
two_count += abs(two[c]-arr[c])
if one_count > two_count:
return two_count
return one_count
arr1 = [5,4,1]
arr2 = [1,6,7,8,9]
s1 = Solution1()
print("方法1:",s1.move_count(arr1))
print("方法1:",s1.move_count(arr2))
# 方法2:arr减相应位置的等差数列
class Solution2:
def move_count(self,arr):
arr = sorted(arr)
one_count = 0
two_count = 0
for c in range(len(arr)):
one_count += abs(arr[c]-(2*c+1))
two_count += abs(arr[c]-(2*c+2))
if one_count < two_count:
return one_count
return two_count
s2 = Solution2()
print("方法2:",s2.move_count(arr1))
print("方法2:",s2.move_count(arr2))
结果:



