在排序前后对具有重复元素的数组进行索引

Question

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

我正在寻找解决方案，或者我正在采取的方法的解决方案。

这里是一个数组

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

有两个2的和两个3的，但如果我与第一2（左一），我想与指数1工作，如果工作我“M与第二2工作，我想与指数6来工作，所以我使用一个辅助阵列中，让我做这件事：

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

，我将在迭代，并使用从a访问每个元素。
我本来可以用each_with_index来完成这个，但是当我排序数组时，问题就开始了。

现在我有一个排序顺序

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

我用sort_by按照排序顺序进行排序a，生产

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

你可以假设输入的所有元素在sort_order存在，以避免sort_by例外。

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

所以我的新助手阵列可能看起来像

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

所以，如果我去这种方法，我将如何产生new_helper阵列，给出原始数组和排序顺序？

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

Answer 1

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

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

那种列表（字典顺序，或者只是忽略了对除第二部分，以随身携带的话）。每对中的第二项告诉你元素在原始数组中的位置。

Answer 2

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

Answer 3

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

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> 

Answer 4

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

无论哪种方式，为什么不使用保存排序值和辅助值的类？然后他们总是在一起，而且你不需要自定义排序算法。

Answer 5

既然你有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 

该算法是基于Counting sort想法，我稍微修改它来保存索引。