arrays - 排列一个整数数组，使得两个连续数字的和不能被 3 整除

Question

我的一个 friend 在对一家公司进行在线评估时遇到了这个问题，并向我提出了这个问题。

An array of integers is given and we have to (possibly) arrange the array such that no two consecutive numbers sum is divisible by 3.

Size of the array n<=10^5.

If no such arrangement is possible then we have to return Not Possible.

我可以想到贪婪地填充整数，这样连续元素的总和如果不能被 3 整除，就会得到 O(n^2)解决方案(但是我不确定贪婪地填充元素是否会在这里给出解决方案)或者我可以考虑做一个(暴力)DFS通过查看所有可能的安排，但这将是一个指数时间的解决方案，并且对于给定的数组大小条件肯定不会在这里工作。

有没有O(nlogn)或O(n)可能的解决方案吗？

Answer 1

是的，存在 O(n) 解:

1. 首先将所有元素分为3个桶，元素x将属于桶x mod 3
2. 现在我们可以使用贪婪策略:注意桶 1 中的元素和2不能是邻居，对于桶 0 中的元素也是如此和0
3. 我们可以放入存储桶 1 中的所有元素进入答案，后跟存储桶 0 中的一个元素以及存储桶 2 中的所有元素
4. 现在只剩下存储桶 0 中的一些元素了我们可以将其放在桶 1 的两个元素之间或桶 2 中的两个元素
5. 当然，有些极端情况是无法解决的