1

这是基本问题：我有一个可能包含重复元素的整数数组。我需要知道每个元素的索引，但是当我对数组进行排序时，每当我从新数组中选择一个元素时，我都希望能够从原始数组中引用相同的元素。

我正在寻找问题的解决方案，或者可能是我正在采取的方法的解决方案。

这是一个数组

a = [1, 2, 3, 4, 3, 5, 2]

有两个 2 和两个 3，但如果我使用第一个2（从左起），我想使用索引 1，如果我使用第二个2，我想使用索引 6。所以我使用一个辅助数组来允许我这样做：

helper = [0, 1, 2, 3, 4, 5, 6]

我将对其进行迭代并使用它来访问a.
我可以用 来完成这个each_with_index，但是当我对数组进行排序时问题就开始了。

现在我有一个排序顺序

sort_order = [2, 4, 1, 5, 3]

我用sort_ordersort_by来排序a，产生

sorted_a = [2, 2, 4, 1, 5, 3, 3]

您可以假设输入中的所有元素都存在sort_order以避免sort_by异常。

现在的问题是我的helper数组应该更新以匹配新位置。每个元素的排序方式应与排序方式相同a，因为不清楚新数组中的前 2 是在索引 1 处还是在原始数组的索引 6 处。

所以我的新辅助数组可能看起来像

new_helper = [1, 6, 3, 0, 5, 2, 4]

new_helper因此，如果我采用这种方法，在给定原始数组和排序顺序的情况下，我将如何生成数组？

也许有更好的方法来做到这一点？

4

5 回答 5

1

我建议先用辅助数组压缩原始数组，根据来自原始数组的组件对压缩数组进行排序，然后解压缩它们（不幸的是，这种方法不存在，但你可以转置）。或者您可以实现自己的排序逻辑，如 Hunter 所指出的。

于 2012-07-25T19:16:04.200 回答
0

当您在主数组中交换时，您需要交换辅助数组中的值。 

loop do
   swapped = false
   0.upto(list.size-2) do |i|
      if list[i] > list[i+1]
         list[i], list[i+1] = list[i+1], list[i] # swap values
         helper[i], helper[i+1] = helper[i+1], helper[i]; #swap helper values
         swapped = true
      end
   end
   break unless swapped
end

例子

irb(main):001:0> def parallel_sort(list, helper)
irb(main):002:1> loop do
irb(main):003:2*    swapped = false
irb(main):004:2>    0.upto(list.size-2) do |i|
irb(main):005:3*       if list[i] > list[i+1]
irb(main):006:4>          list[i], list[i+1] = list[i+1], list[i] # swap values
irb(main):007:4>          helper[i], helper[i+1] = helper[i+1], helper[i]; #swap helper values
irb(main):008:4*          swapped = true
irb(main):009:4>       end
irb(main):010:3>    end
irb(main):011:2>    break unless swapped
irb(main):012:2> end
irb(main):013:1> return [list, helper]
irb(main):014:1> end
=> nil
irb(main):015:0> a = [3,2,1]
=> [3, 2, 1]
irb(main):016:0> b = ["three","two","one"]
=> ["three", "two", "one"]
irb(main):017:0> parallel_sort(a,b)
=> [[1, 2, 3], ["one", "two", "three"]]
irb(main):018:0>
于 2012-07-25T19:18:10.990 回答
0

在循环内排序很少是一个好主意......如果你这样做，你可能会更好地使用treap（平均速度快，但很少有操作需要一段时间）或红黑树（相对较慢，但给出了相当一致的操作时间）。这些很像哈希表，除了它们没有那么快，并且它们使用树来保持元素按顺序存储。

无论哪种方式，为什么不使用一个既保存排序依据的值又保存辅助值的类呢？然后它们总是在一起，您不需要自定义排序算法。

于 2012-07-25T20:53:08.553 回答
0

制作成对的原始数据和该数据的索引的列表。像这样：

a = [(1, 0), (2, 1), (3, 2), (4, 3), (3, 4), (5, 5), (2,6)]

对该列表进行排序（按字典顺序，或者只是忽略该对的第二部分，除非随身携带）。每对中的第二项告诉您元素在原始数组中的位置。

于 2012-07-26T03:15:55.600 回答
0

既然你有sort_order，你的数组已经排序了，所以我们应该利用这个事实作为一个优势。我想出了这个简单的解决方案：

a = [1, 2, 3, 4, 3, 5, 2]
sort_order = [2, 4, 1, 5, 3]

# Save indices
indices = Hash.new { |hash, key| hash[key] = [] }
a.each_with_index { |elem, index| indices[elem] << index }

# Sort the array by placing elements into "right" positions
sorted = []
helper = []
sort_order.each do |elem|
  indices[elem].each do |index|
    sorted << elem
    helper << index
  end
end

p sorted
p helper

该算法基于计数排序的思想，我稍微修改它以保存索引。

于 2012-07-26T04:02:48.383 回答