牛牛满意的数组(二）

[编程题]牛牛满意的数组(二）

热度指数：116 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛牛有一个数组 $a$ ，在他看来，如果这个数组满足对于任意的下标 $i$ ，都有 $i \% 2 = a[i] \% 2$ ，那么他对这个数组十分满意。

只不过天不遂人愿，并不是所有的数组都满足这样的条件，但是，牛牛可以通过交换数组中的某些元素使得该数组满足以上情况。

给定一个数组 $a$ ，如果能通过交换数组中的某些元素使得该数组让牛牛十分满意，请返回牛牛需要最少交换的次数，否则，请返回-1。

请注意，数组下标从0开始。

示例1

输入

1,[3]

输出

-1

说明

很显然，3%2 != 0%2，而且无法进行任何的交换，所以返回-1。

示例2

输入

3,[5,4,6]

输出

说明

我们可以交换第一个元素和第二个元素，使得数组变成[4,5,6]，交换后的数组是牛牛满意的，返回最少交换次数1。

备注:

算法知识视频讲解

牛客377646584号

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 如果能通过交换数组中的某些元素使得该数组让牛牛十分满意，请返回牛牛需要最少交换的次数，否则，请返回-1。
# @param n int整型代表数组中元素的数量
# @param a int整型一维数组代表数组中元素的大小
# @return int整型
#
class Solution:
def findArray(self , n , a ):
# write code here
cache0,cache1=[],[]
for i in range(n):
if a[i]%2==0:
cache0.append(a[i])
else:
cache1.append(a[i])
A = len(cache0)
B = len(cache1)
m=0
if (n%2==0 and A==B) or (n%2==1 and A==B+1):
for i in range(n):
if a[i]%2!=i%2:
m+=1
return m//2
return -1

发表于 2021-04-24 15:13:40 回复(0)