問題タブ [union-find]

プリンストンアルゴリズムコースを開始したばかりで、次のようにCで非常に基本的なクイック検索アルゴリズムを実装しようとしました-

プログラムは想定どおりに実行されていません。a を実行してから a を実行しようとするunion(4,3)と、その値union(3,8)のみが変更され、 は変更されません。また、なぜ使用しなければならなかったのかわかりません（プログラムはそれなしで終了し続けました）。arr[3]arr[4]getchar

だから私は面接の練習問題をやっていて、これに出くわしました: 文字列 str と、文字列内のどのインデックスを交換できるかを示すペアの配列が与えられた場合、許可された交換を行った結果、辞書編集的に最大の文字列を返します。インデックスは何度でも交換できます。

例

str = "abdc" およびpairs = [[1, 4], [3, 4]] の場合、出力は swapLexOrder(str,pairs) = "dbca" になります。

指定されたインデックスを交換すると、文字列 "cbda"、"cbad"、"dbac"、"dbca" が得られます。このリストで辞書順で最大の文字列は「dbca」です。

組合を見つけることに関する実用的な答えがありますが、私の答えは遅すぎます:

誰かが私のコードを微調整して速度を上げるのを手伝ってくれませんか? 私が持っているコードは次のとおりです。

おそらくユニオンを見つけるために使用している関数ですが、ハッシュを作成せずにそれを行うことができるのではないかと考えていましたか? また、問題を解決するためのより良い方法を知っている場合は、常に何か新しいことを学びたいと思っています. ありがとう！

私は組合の発見に取り組んでいます。インデックスの 1 つが別のペアのインデックスと数値を共有しているかどうかに基づいて、数値のペアをグループ化したいと考えています。そう：

次のようなペアの配列があります。

このようなユニオンでそれらをグループ化する最良の方法は何ですか:

([1,3] と [3,8] は 3 を共有するため一緒になります。そのグループは 8 を共有するため [6,8] と結合します。javascript でこれを行う最良の方法は何ですか?

他の例を次に示します。

編集 私が現在使用している方法は次のとおりです。