至少不需要交换，以确保没有两只猫或狗在相邻的地方

Question

我们得到一个数组，数组中的元素代表猫和狗。我们必须通过交换来重新排列元素，使得没有两只猫或狗在相邻的地方。

注意：我们可以将数组的一个元素与任何元素交换。

Eg: given input: [d,c,d,c,c]
exp o/p: 2
Explanation : 
step 1: swap index-0 and index-1 =>[c,d,d,c,c]
step 2: swap index2 and index-3  =>[c,d,c,d,c]

input: [c,d,d,c,c,c]
exp o/p : not possible

Answer 1

1. 检查它们中的任何一个是否为n==m 1或n==m是否为true。
2. 如果情况不是这样，则不可能返回。
3. 如果n==m1，我们知道在所有偶数索引上必须有一个n，对于所有奇数索引，必须有一个m。
4. 编辑：如果n==m初始值很重要！如果交换的数量是算法中最重要的部分，请在两种可能的变体上运行第5步，并比较结果子数组的长度。[1]谢谢@Ishpreet指出这一点！
5. 遍历数组，检查是否有n或m。如果相应索引的值是错误的（例如，在索引0上有一个m而不是n，请注意数组中错误放置的n或m的索引是向下的。
6. 之后，根据两个子数组交换数组中写下来的索引值。

[C，C，C，C，D，D，D，D]

错误C=[1,3]

错误的D=[4,6]

交换（1,4）和（3,6）

结果：[C， D， C， D， C， D， C， D]

[1] 算法的复杂性不会因此而改变。