배열 정렬 및 색인 유지

Question

Arrays.sort(array);을 사용하면 배열을 정렬하는 매우 쉬운 방법입니다. 그러나 문제가 있습니다. 정렬되지 않은 각 배열에 대해 다른 데이터 구조의 객체를 나타내는 인덱스가 있습니다. 위의 코드 또는 다른 유사한 방법을 사용하여 배열을 정렬 할 때 각 값의 인덱스가 변경됩니다. 각 값의 할당 된 인덱스를 갖는 솔루션이 있습니까? 어레이의 동일한 값이 많이 존재하기 때문에

EDIT

HashMap<Key, Value> 사용 유용하지 않을 것이다.

Answer 1

두 데이터 구조를 병렬로 정렬하십시오.

또는 참조 인덱스 (다른 데이터 구조 참조)를 각 요소의 내부 필드로 만들어 정렬 순서에 따라 요소의 순서가 변경 되더라도 각 요소가 동일한 "참조 인덱스"를 유지하도록합니다.

또는 더 나은 점은 각 요소에 다른 데이터 구조의 요소에 대한 직접적인 참조 변수 인 내부 필드 만 제공하는 것입니다. 예를 들어

(당신이 어떤 이유로 원시 인덱스 자체와 연관된 객체/값뿐만 아니라 참조가 필요하지 않은 경우) : 해당 인덱스의 요소와 두 개의 병렬 배열을 가진 this SO Q&A

Answer 2

먼저, 당신은 할 수 있습니다 나타냅니다 두 개의 필드가 들어있는 컨테이너 객체를 사용하여 데이터 구조를 단일 배열로 변경합니다. 이 컨테이너 객체는 Comparable 인터페이스를 구현합니다.

하지만, 당신이 무슨 말을 고집, 하나의 접근 방법은 수 :

/** 
* 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은 키의 수입니다. 적어도 최악의 경우는 없습니다.