如何高效映射ActiveRecord数组，避免赞助元素连续出现？

核心思路 #

由于赞助内容集中在数组前部，最直接高效的方式是先分离赞助与非赞助内容，再按「赞助+至少一个非赞助」的规则穿插合并，确保赞助内容不会连续出现。这种方法的时间复杂度为O(n)，空间复杂度为O(n)，是理论上的最优解（必须遍历所有元素一次，且需要存储结果）。

具体实现（Ruby示例） #

# 1. 分离赞助和非赞助内容
sponsored = contents.select { |content| content.sponsored? }
non_sponsored = contents.reject { |content| content.sponsored? }

# 2. 穿插合并两个数组
result = []
spon_idx = 0
non_idx = 0

# 先遍历所有赞助内容，每个赞助后至少跟一个非赞助
while spon_idx < sponsored.size
  result << sponsored[spon_idx]
  spon_idx += 1

  # 若还有非赞助内容，加入一个作为分隔
  if non_idx < non_sponsored.size
    result << non_sponsored[non_idx]
    non_idx += 1
  end
end

# 加入剩余的非赞助内容
result += non_sponsored[non_idx..-1]

逻辑说明 #

1. 分离阶段：通过一次遍历将数组拆分为sponsored（赞助内容）和non_sponsored（普通内容）两个子数组，这一步时间复杂度为O(n)。
2. 合并阶段：用双指针分别遍历两个子数组，每加入一个赞助内容后立即加入一个普通内容（如果还有剩余），确保赞助内容不会连续。最后将剩下的普通内容追加到结果末尾即可。

为什么这是最高效的？ #

• 时间上：整个过程只需要两次线性遍历（分离+合并），总时间复杂度为O(n)，没有嵌套循环或复杂计算。
• 空间上：虽然需要额外存储两个子数组，但这是实现该需求的必要开销（若尝试原地修改，插入元素会导致O(n²)的时间复杂度，反而更低效）。
• 逻辑简洁：代码可读性强，易于维护和扩展（比如后续需要调整赞助内容的分布密度，只需修改合并阶段的规则即可）。

示例验证 #

针对你给出的输入：

contents = [
  { id: 1, sponsored: true },
  { id: 2, sponsored: true },
  { id: 3, sponsored: false },
  { id: 4, sponsored: false },
  { id: 5, sponsored: false },
  { id: 6, sponsored: false }
]

运行代码后得到的结果为：

[
  { id: 1, sponsored: true },
  { id: 3, sponsored: false },
  { id: 2, sponsored: true },
  { id: 4, sponsored: false },
  { id: 5, sponsored: false },
  { id: 6, sponsored: false }
]

该结果满足「赞助内容不连续」的要求，与你的目标示例逻辑一致（只是普通内容的顺序略有差异，若需要完全匹配示例顺序，只需调整合并时取普通内容的顺序即可，但核心逻辑不变）。

内容的提问来源于stack exchange，提问作者Roberto Pezzali