在排序前後對具有重複元素的數組進行索引

這是基本問題：我有一個可能具有重複元素的整數數組。我需要知道每個元素的索引，但是當我對數組進行排序時，無論何時從新數組中選擇一個元素，我都希望能夠引用原始數組中的相同元素。在排序前後對具有重複元素的數組進行索引

我正在尋找解決方案，或者我正在採取的方法的解決方案。

這裏是一個數組

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陣列，給出原始數組和排序順序？

也許有更好的方法來做到這一點？

來源

2012-07-25 MxyL

只要該元素的值相同，輔助數組是否指向與原始元素不同的元素，這有什麼關係？ – 2012-07-25 18:46:43

這些值並不重要（在我使用它們的方法的上下文中），但是位置是。這就是我創建我的幫助程序數組時所想到的，所以新的幫助程序數組應該指向相同的元素。 – MxyL 2012-07-25 19:11:16

然後，您需要自己實現排序邏輯，並且每當您交換數組中的某個位置時，也將它交換到您的幫助程序數組中。 – 2012-07-25 19:13:49

製作原始數據和數據索引對的列表。就像這樣：

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

那種列表（字典順序，或者只是忽略了對除第二部分，以隨身攜帶的話）。每對中的第二項告訴你元素在原始數組中的位置。

來源

2012-07-26 03:15:55

我建議先用輔助數組壓縮原始數組，然後根據來自原始數組的組件對壓縮數組進行排序，然後解壓縮它們（不幸的是，這種方法不存在，但可以進行轉置）。或者你可以像Hunter指出的那樣實現你自己的排序邏輯。

來源

2012-07-25 19:16:04 sxu

當您在主數組中交換時，您需要交換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>

來源

2012-07-25 19:18:10

雖然排序順序基於自定義排序順序數組，但我不確定如何有效地實現這種排序。但這個想法很有效。我希望只是使用'sort_by'爲我完成任務。 – MxyL 2012-07-25 19:27:35

@Keikoku只要你沒有對成千上萬的元素進行排序，我在上面發佈的內容確實很好。 – 2012-07-25 19:54:18

一個循環內排序是很少一個好主意....如果你這樣做，你可能會更好（平均快速，但很少有操作需要一段時間）或紅黑樹（相對較慢，但操作時間相當一致）。這些很像哈希表，除了它們不如速度快，並且它們使用樹來保存按順序存儲的元素。

無論哪種方式，爲什麼不使用保存排序值和輔助值的類？然後他們總是在一起，而且你不需要自定義排序算法。

來源

2012-07-25 20:53:08 user1277476

是的，這是我原來的設計非常糟糕的解決方案。但我想象有人可能遇到這種問題，他們沒有改變設計的選擇。 – MxyL 2012-07-26 02:43:50

既然你有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想法，我稍微修改它來保存索引。

來源

2012-07-26 04:02:48 galymzhan

在排序前後對具有重複元素的數組進行索引

回答

相關問題