参考证明
对于长度为n的数组arr，先使用counter统计每个数的频率。找到最大频率的数k，记该频率为m。
- 当
m > n//2时，无法配对使每两个元素各不相同。 - 从偶数位开始加入
k，然后再按频率从大到小顺序继续加入剩下的数，触底即从奇数位从头开始。确保与偶数位相邻的奇数位的数都与偶数位的数不同。 反证，令偶数位相邻的奇数位的数都与偶数位的数同，记narr[even - 1] = narr[even]或者narr[even] = narr[even + 1]那么得知该数的频率至少为(n - even + 1)// 2 + (even + 1)//2 >= n//2。那么当even = 0时，该数的频率违背了1，即该数频率大于n//2。 当even != 0时，即前面有一个数的频率>= n//2同样的违背了1.