配列をソートしてインデックスを維持する

Question

Arrays.sort(array);を使用すると、配列をソートするのに非常に簡単な方法です。しかし問題がある。ソートされていない配列ごとに、他のデータ構造のオブジェクトを参照するインデックスがあります。上記のコードまたは他の同様の方法を使用して配列をソートすると、各値のインデックスが変更されます。各値の割り当てられたインデックスを持つソリューションはありますか？配列内の同じ値がたくさんあるので、

EDIT

HashMap<Key, Value>を使用することは有用ではないだろう。

Answer 1

両方のデータ構造を並行してソートします。

また、要素の順序がソートによって変更されても、各要素が同じ「参照インデックス」を維持するように、（他のデータ構造を参照するための）参照インデックスを各要素の内部フィールドにします。

さらに、各要素に、他のデータ構造内の要素への直接参照変数である内部フィールドを渡すだけです。例えば

（あなたには、いくつかの理由のために生のインデックス自体及び関連するオブジェクト/値だけでなく、参照必要がない場合）、対応するインデックスの要素を有する2つの平行アレイを有するthis SO Q&A

Answer 2

まず、希望するかもしれない示し2つのフィールドを含むコンテナオブジェクトを使用してデータ構造を単一の配列に変更します。このコンテナオブジェクトは、Comparableインタフェースを実装します。

しかし、あなたの言うことに固執、1つのアプローチは次のようになります。

/** 
* Sorts parallel arrays in-place. Sorted by the first array and updating 
* all other arrays to match. 
* Uses the natural sorting of the objects. 
* All arrays must be the same length. 
* 
* @param keys   the values used to sort, may be duplicate 
* 
* @param otherArrays the arrays to have reordered to match the sorting of 
*      the keys array. 
* 
* @exception IllegalArgumentException if any of otherArrays have a length 
*      different that the keys array. 
*/ 
public static <E extends Comparable<? super E>> void sortParallelArrays(
    E[] keys, 
    Object[] ... otherArrays 
) { 
    int numKeys = keys.length; 
    int numOtherArrays = otherArrays.length; 
    for(Object[] otherArray : otherArrays) { 
     if(otherArray.length != numKeys) { 
      throw new IllegalArgumentException("Mismatched array lengths"); 
     } 
    } 
    // A list of all indexes per key 
    // This also does the sorting within the TreeMap using natural ordering 
    SortedMap<E, List<Integer>> originalIndexesByKey = new TreeMap<E, List<Integer>>(); 

    // Populate the map 
    for(int i = 0; i < numKeys; i++) { 
     E key = keys[i]; 
     List<Integer> originalIndexes = originalIndexesByKey.get(key); 
     if(originalIndexes == null) { 
      // Optimization for the non-duplicate keys 
      originalIndexesByKey.put(key, Collections.singletonList(i)); 
     } else { 
      if(originalIndexes.size() == 1) { 
       // Upgrade to ArrayList now that know have duplicate keys 
       originalIndexes = new ArrayList<Integer>(originalIndexes); 
       originalIndexesByKey.put(key, originalIndexes); 
      } 
      originalIndexes.add(i); 
     } 
    } 

    // Store back to keys and sort other arrays in a single traversal 
    Object[][] sortedOtherArrays = new Object[numOtherArrays][numKeys]; 
    int pos = 0; 
    for(Map.Entry<E, List<Integer>> entry : originalIndexesByKey.entrySet()) { 
     E key = entry.getKey(); 
     for(int index : entry.getValue()) { 
      keys[pos] = key; 
      for(int ooIndex = 0; ooIndex < numOtherArrays; ooIndex++) { 
       sortedOtherArrays[ooIndex][pos] = otherArrays[ooIndex][index]; 
      } 
      pos++; 
     } 
    } 
    assert pos == numKeys : "Arrays should be full"; 

    // Copy back to original arrays for in-place sort 
    for(int ooIndex = 0; ooIndex < numOtherArrays; ooIndex++) { 
     System.arraycopy(
      sortedOtherArrays[ooIndex], 0, 
      otherArrays[ooIndex], 0, 
      numKeys); 
    } 
} 

これは、ほとんどのメモリ効率的な戦略ではありませんが、多くのコードではありません。

時間の複雑さはそれほど悪くありません。 O((M+1)*N*log(N))のようになります。MはotherArraysの数、Nは鍵の数です。最低でも狂った最悪の問題はありません。