Получите индексы массива после сортировки?

Question

Предположим, пользователь вводит массив, например:

Array = {France, Spain, France, France, Italy, Spain, Spain, Italy} 

, которую я знал, длина его

index массив будет:

index = {0, 1, 2, 3, 4, 5, 6, 7} 

Теперь, после сортировки его с помощью Arrays.sort(Array);

newArray будет следующим:

newArray = {France, France, France, Italy, Italy, Spain, Spain, Spain} 

и newIndex будет:

newIndex = {0, 2, 3, 4, 7, 1, 5, 6} 

Проблема: как я могу найти newIndex из входного массива?

Заранее спасибо

Answer 1

Не сортирует массив, чтобы начать с. Сортируйте индексный массив, передавая в компаратор, который сравнивает значения, используя их как индексов в массиве. Таким образом, вы получаете newIndex в результате сортировки, и оттуда тривиально перейти к отсортированному массиву фактических элементов.

Правда, что означает сортировку массива целых чисел в пользовательском пути - что означает либо с использованием Integer[] и стандартной библиотеки Java, или 3-ю библиотеку партии, которая имеет интерфейс «IntComparator», который может быть использован в сочетании с sort(int[], IntComparator) тип метода.

EDIT: Хорошо, вот пример компаратора. Для простоты я предполагаю, что вы хотите только отсортировать «исходный» массив строк ... и я не буду утруждать себя тестированием недействительности.

public class ArrayIndexComparator implements Comparator<Integer> 
{ 
    private final String[] array; 

    public ArrayIndexComparator(String[] array) 
    { 
     this.array = array; 
    } 

    public Integer[] createIndexArray() 
    { 
     Integer[] indexes = new Integer[array.length]; 
     for (int i = 0; i < array.length; i++) 
     { 
      indexes[i] = i; // Autoboxing 
     } 
     return indexes; 
    } 

    @Override 
    public int compare(Integer index1, Integer index2) 
    { 
     // Autounbox from Integer to int to use as array indexes 
     return array[index1].compareTo(array[index2]); 
    } 
} 

Вы бы использовать его как это:

String[] countries = { "France", "Spain", ... }; 
ArrayIndexComparator comparator = new ArrayIndexComparator(countries); 
Integer[] indexes = comparator.createIndexArray(); 
Arrays.sort(indexes, comparator); 
// Now the indexes are in appropriate order. 

Answer 2

Одним из способов вы можете сделать это обернуть исходный индекс и название страны, в отдельный класс. Затем отсортируйте массив по именам. Таким образом, ваши исходные индексы будут сохранены.

Answer 3

TreeMap<String,Int> map = new TreeMap<String,Int>(); 
for(int i : indexes) { 
    map.put(stringarray[i], i); 
} 

Теперь итератор над map.values ​​(), чтобы получить индексы в порядке сортировки, а над map.keySet(), чтобы получить строки, или через map.entrySet(), чтобы получить строковые индексные пары ,

Answer 4

Что приходит на первый взгляд Карта им нравится, что

Map <Integer, String> map = new HashMap<Integer, String>(); 
map.put(0, "France"); 
map.put(1, "Spain"); 
map.put(2, "France"); 

, а затем отсортировать их по значению like that, а затем вы можете знать их индексы и значения (ключ, значения) просто распечатать карту

Iterator mapIterator = map.keySet().iterator(); 

while (mapIterator .hasNext()) { 
    String key = mapIterator.next().toString(); 
    String value = map.get(key).toString(); 

    System.out.println(key + " " + value); 
} 

Answer 5

Краткий способ достижения этой цели с Java 8 Стрит API,

final String[] strArr = {"France", "Spain", "France"}; 
int[] sortedIndices = IntStream.range(0, strArr.length) 
       .boxed().sorted((i, j) -> strArr[i].compareTo(strArr[j])) 
       .mapToInt(ele -> ele).toArray(); 

Answer 6

Я сделал следующее на основе кода @ Skeet.Я думаю, что это немного больше ООПи. Не знаю.

public static <T extends Comparable<T>> List<Integer> sortIndex(List<T> in) { 
    ArrayList<Integer> index = new ArrayList<>(); 
    for (int i = 0; i < in.size(); i++) { 
     index.add(i); 
    } 

    Collections.sort(index, new Comparator<Integer>() { 
     @Override 
     public int compare(Integer idx1, Integer idx2) { 
      return in.get(idx1).compareTo(in.get(idx2)); 
     } 
    }); 

    return index; 
} 

Вместо того класс, который реализует сортировку и индексация, имеющий код компаратора для различных объектов, поступающих в объектах в исходном массиве должны реализовать интерфейс Сопоставимого. Кажется, что многие объекты, представляющие интерес, имеют естественный порядок и уже реализован интерфейс Comparable.

public static void main(String[] args) { 

    List<Integer> a1 = new ArrayList<>(Arrays.asList(2, 3, 9, 4, 1)); 
    // Just pass in the list to have its indexes sorted by the natural ordering 
    List<Integer> idx = sortIndex(a1); 

    List<Double> a2 = new ArrayList<>(Arrays.asList(1.0, 5.3, 5.2, -3.1, 0.3)); 
    idx = sortIndex(a2); 

    List<numBits> a3 = new ArrayList<>(); 
    for (int i = 0; i < 10; i++) { 
     a3.add(new numBits(i)); 
    } 

    // If you need to sort the indexes of your own object, you must implement 
    // the Comparable Interface. 
    idx = sortIndex(a3); 
} 

static class numBits implements Comparable<numBits> { 
    private int a; 

    public numBits(int i) { 
     a = i; 
    } 

    public String toString() { 
     return Integer.toString(a); 
    } 

    // Sort by the total number of bits in the number. 
    @Override 
    public int compareTo(numBits that) { 
     if (Integer.bitCount(this.a) < Integer.bitCount(that.a)) 
      return -1; 
     if (Integer.bitCount(this.a) > Integer.bitCount(that.a)) 
      return 1; 
     return 0; 
    } 
} 

Answer 7

Если иметь сценарий неоднократно сортировок примитивные терок или ИНТ массивов с положительными значениями, то метод, как ниже, дает гораздо лучше (x3 ~ x4) скорость по сравнению с использованием любых компараторов:

long time = System.currentTimeMillis(); 
for (int i = 0; i < iters; i++) {   
    float[] array = RandomUtils.randomFloatArray(-1, 1, 3000); 
    long[] valueKeyPairs = new long[array.length]; 
    for (int j = 0; j < array.length; ++j) { 
     valueKeyPairs[j] = (((long) Float.floatToIntBits(array[j])) << 32) | (j & 0xffffffffL); 
    } 
    Arrays.sort(valueKeyPairs); 
    /**Then use this to retrieve the original value and index*/ 
    //long l = valueKeyPairs[j]; 
    //float value = Float.intBitsToFloat((int) (l >> 32)); 
    //int index = (int) (l); 
} 
long millis = System.currentTimeMillis() - time;