1

これが基本的な問題です。要素が重複している可能性のある整数の配列があります。各要素のインデックスを知る必要がありますが、配列を並べ替えるときに、新しい配列から要素を選択するたびに、元の配列から同じ要素を参照できるようにしたいと考えています。

問題の解決策、または私が取っているアプローチの解決策を探しています。

ここに配列があります

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

2 が 2 つと 3 が 2 つありますが、1 つ目2(左から) を使用する場合はインデックス 1 を使用し、2 つ目を使用する場合2はインデックス 6 を使用したいと考えています。したがって、ヘルパー配列を使用してこれを実行できるようにします。

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

これを反復して、 から各要素にアクセスするために使用しますa。
でこれを達成できたかもしれませんeach_with_indexが、問題は配列をソートするときに始まります。

今、私はソート順を持っています

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

私はsort_order に従ってsort_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

最初に元の配列をヘルパー配列で圧縮し、元の配列からのコンポーネントに従って圧縮された配列をソートし、解凍することをお勧めします (この方法は残念ながら存在しませんが、転置できます)。または、ハンターが指摘した独自の並べ替えロジックを実装することもできます。

于 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

があるので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-26T04:02:48.383 に答える
0

元のデータとそのデータのインデックスのペアのリストを作成します。このような：

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

そのリストを並べ替えます (辞書順、またはペアの 2 番目の部分をそのまま無視します)。すべてのペアの 2 番目の項目は、要素が元の配列のどこにあったかを示します。

于 2012-07-26T03:15:55.600 に答える
0

ループ内でソートすることはめったに良い考えではありません....そうしている場合は、treap（平均して高速ですが、操作に時間がかかることはめったにありません）または赤黒ツリー（比較的遅いですが、しかしかなり一貫した操作時間を提供します）。これらはハッシュテーブルに似ていますが、それほど高速ではなく、ツリーを使用して要素を順番に格納します。

いずれにせよ、ソートする値とヘルパー値の両方を保存するクラスを使用してみませんか? その後、それらは常に一緒になり、カスタムの並べ替えアルゴリズムは必要ありません。

于 2012-07-25T20:53:08.553 に答える