我的一个朋友在一家公司的在线评估中遇到了这个问题，并问了我这个问题。
给出了一个整数数组，我们必须（可能）安排该数组，以使两个连续的数字之和不能被3整除。
数组
n<=10^5的大小。如果没有这种安排，那么我们必须返回
Not Possible。
我可以想到贪婪地填充整数，这样连续的元素之和如果不能被3整除，将得到一个O(n^2)解决方案（但是，我不确定贪婪地填充元素是否会得出解决方案），或者我可以考虑通过查找所有可能的安排来做一个（bruteforce）DFS，但这将是一个指数时间解决方案，对于给定的数组大小条件，在这里肯定是行不通的。
有没有O(nlogn)或O(n)解决方案？
是的，存在O（n）解决方案：
x将属于存储桶x mod 3 1和2中的元素不能是邻居，对于桶0和0中的元素也是如此1中的所有元素放入答案中，然后是桶0中的一个元素以及桶2中的所有元素0中的一些元素，我们可以将它们放在存储桶1的两个元素之间或存储桶2的两个元素之间算法：将数字分为三组：组0 = 0模3，组1 = 1模3，组2 = 2模3。令n0，n1，n2为组0、1或3中的元素数。 2。
组1和2的元素必须由组0的元素分隔：如果n0 = 0，并且n1> 0和n2> 0都没有解。如果n0 = 0，并且n1 = 0或n2 = 0或两者兼而有之，则无需执行任何操作。
让n = n0-1。我们需要第1组和第2组的n个元素来分隔第0组的项目：如果n> n1 + n2，则没有解。
现在0≤n≤n1 + n2。令m = min（n1，n）。从n1-组1的m个元素开始，然后是m对（组0的元素，组1的元素），然后是（n-m）对（组0的元素，组2的元素），然后是最后一个组0的元素，然后是组2的其余n2-（n-m）个元素。