时间戳

首页 > 解决方案 > 排列一个整数数组，使得没有两个连续数字的总和可以被 3 整除

arrays - 排列一个整数数组，使得没有两个连续数字的总和可以被 3 整除

问题描述

我的一个朋友在一个公司的在线评估中遇到了这个问题，并问了我这个问题。

给定一个整数数组，我们必须（可能）排列数组，使得没有两个连续数字的总和可以被 3 整除。

数组的大小n<=10^5。

如果没有这样的安排是可能的，那么我们必须返回Not Possible。

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

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

标签： arraysalgorithm

解决方案

是的，存在 O(n) 解决方案：

  1. 首先将所有元素分成3个桶，元素x将属于桶x mod 3
  2. 现在我们可以使用贪心策略：注意桶中的元素1和2不能是邻居，桶中的元素0和0
  3. 我们可以将桶中1的所有元素放入答案中，然后是桶中的一个元素和桶中0的所有元素2
  4. 现在剩下的就是桶0中的一些元素，我们可以将它们放在桶的1两个元素或桶中的两个元素之间2
  5. 当然有一些极端情况是不可能解决的

推荐阅读