如何对整数数组进行排序，同时将相同的元素彼此分开？

Question

我不确定是否有这种类型的名称，所以我正在努力在其他地方找到任何相关答案。

我希望元素尽可能旋转。

给出这个数组：

[38, 38, 40, 40, 40, 41, 41, 41, 41, 60]

我该如何分类？

[38, 40, 41, 60, 38, 40, 41, 40, 41, 41]

我研究了其他主题，但未能找到答案。

提前致谢！

Answer 1

这本身并不是真正的 "sort"。有一个排序 step，但最终你真正想做的是 matrix transposition.

下面有两种实现方法。

更详细

第一种方法较长，为了清楚起见（希望如此）分解为更多步骤。

首先，我们将对相关的数组元素进行排序和分组：

v = arr.sort.group_by { |e| e }.values
# => [[38, 38], [40, 40, 40], [41, 41, 41, 41], [60]]

让我们为结果创建一个新数组：

r = []

现在我们将得到元素数量最多的那个：

max = arr.map { |e| arr.count(e) }.max

然后我们将遍历数组多次，

max.times { ... }

每次从每个子数组中取出一个元素，然后将其放入结果数组中：

max.times { v.each { |a| r << a.shift } }; r.compact!

我们得到了答案：

# => [38, 40, 41, 60, 38, 40, 41, 40, 41, 41]

更简洁

既然您已经了解了很长的路要走，这里有一个更简洁的方法。这不需要太多的迭代（或输出数组！）。

首先，我们将子数组填充到 max:

的大小

arr.sort.
  group_by { |e| e }.values.
  map { |a| a.fill(nil, a.size..max-1) }
# ...

现在这是一个大小为 max × max 个元素的方阵，因此我们可以将其视为方阵。这意味着我们可以转置元素，使 "rows" 变为 "columns"，反之亦然。

所以我们将 transpose，然后 flatten 得到一个数组，然后 compact 去掉 nil 个元素：

# ...
  (...).transpose.flatten.compact

我们得到了想要的结果：

# => [38, 40, 41, 60, 38, 40, 41, 40, 41, 41]

Answer 2

这是另一种方法。看来约翰已经给出了很好的答案，所以我不打算详细解释。

要了解这是如何工作的，我建议放入一些 puts 语句来查看中间值。您可以运行它和 watch ruby sorter_test.rb 以不断获得反馈。（参见 watch docs）。

这里使用的大部分方法都来自Enumerable module.

require 'minitest/autorun'

class Sorter < Struct.new(:list)
  def call
    sorted_and_grouped = list.sort.group_by { |i| i }.values
    max_len = sorted_and_grouped.max_by(&:count).count
    padded = sorted_and_grouped.map { |xs| pad(xs, max_len) }
    padded.reduce(&:zip).flatten.compact
  end

  private

  def pad(xs, len)
    xs.fill(nil, xs.count...len)
  end
end

ORIGINAL  = [38, 38, 40, 40, 40, 41, 41, 41, 41, 60].freeze
SORTED    = [38, 40, 41, 60, 38, 40, 41, 40, 41, 41].freeze
class TestSorter < Minitest::Test
  def test_sorts_as_expected
    actual = Sorter.new(ORIGINAL).call
    assert_equal SORTED, actual
  end
end

Answer 3

这是另一种方式。这取决于你的数组被排序（增加或减少），就像你的例子一样。此外，如果没有这个假设，问题就没有明确定义。

首先，我希望得到的帮手是：

class Array
  def %(arr)
    arr.each_with_object(dup) do |e,a|
      i = a.index(e)  
      a.delete_at(i) if i
    end
  end
end

例如：

arr = [38, 38, 40, 40, 40, 41, 41, 41, 41, 60]
arr % [41, 60, 40, 38, 40, 41] 
  #=> [38, 40, 41, 41]

如果 a 和 b 是两个数组，a%b 类似于 a-b，只是不删除包含的 a 的所有元素在 b 中，对于 b 中该字符的每个实例，它会删除 a 中的一个字符（具有最小索引的字符）。现在这不是一个方便的内置方法吗？

有了这个助手，按照所需的方式对数组进行排序是一件简单的事情：

复制数组 a 并创建一个空数组 result。
将 ua 的独特元素添加到 result。
使用助手从 a 中删除 u。
如果a为空，returnresult；否则重复步骤 2。

代码如下：

def steves_sort(arr)
  a = arr.dup
  result = []
  while a.any?
    u = a.uniq
    result.concat(u)
    a = a % u
  end
  result
end

steves_sort([38, 38, 40, 40, 40, 41, 41, 41, 41, 60])
  #=> [38, 40, 41, 60, 38, 40, 41, 40, 41, 41]

如何对整数数组进行排序，同时将相同的元素彼此分开？

How do I sort an integer array while also keeping identical elements apart from each other?

ruby

arrays

sorting

更详细

更简洁