Индексная проблема сортировки в Java

Question

Это требование, когда я сталкиваюсь с проблемой при поиске решения.

Проблема:

У меня есть ArrayList с данными 20, 10, 30, 50, 40, 10.

Если мы отсортируем это в порядке возрастания, результат будет 10, 10, 20, 30, 40, 50.

Но мне нужен результат как 3, 1, 4, 6, 5, 2 . (Индекс каждого элемента после сортировки).

Строго это должно работать, даже если в списке есть повторяющиеся элементы.

Пожалуйста, поделитесь своей идеей / подходом к решению этой проблемы.

Answer 1

Вот мое решение. Мы определяем компаратор для сортировки списка индексов на основе соответствующего объекта в списке. Это дает нам список индексов, который фактически является картой: indices[i] = x означает, что элемент в местоположении x в исходном списке находится в элементе i в отсортированном списке. Затем мы можем достаточно легко создать обратное отображение.

Выходные данные - индексы, начинающиеся с 0: [2, 0, 3, 5, 4, 1]

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

class LookupComparator<T extends Comparable<T>> implements Comparator<Integer> {
    private ArrayList<T> _table;
    public LookupComparator(ArrayList<T> table) { 
        _table = table; 
    }
    public int compare(Integer o1, Integer o2) {
        return _table.get(o1).compareTo(_table.get(o2));
    }
}

public class Test {

    public static <T extends Comparable<T>> ArrayList<Integer> indicesIfSorted(ArrayList<T> list) {
        ArrayList<Integer> indices = new ArrayList<Integer>();
        for (int i = 0; i < list.size(); i++)
            indices.add(i);
        Collections.sort(indices, new LookupComparator(list));

        ArrayList<Integer> finalResult = new ArrayList<Integer>();
        for (int i = 0; i < list.size(); i++)
            finalResult.add(0);
        for (int i = 0; i < list.size(); i++)
            finalResult.set(indices.get(i), i);
        return finalResult;
    }

    public static void main(String[] args) {

        ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(20);
        list.add(10);
        list.add(30);
        list.add(50);
        list.add(40);
        list.add(10);

        ArrayList<Integer> indices = indicesIfSorted(list);
        System.out.println(indices);


    }


}

Answer 2

Упрощенным подходом будет сортировка списка;затем зациклите исходный список, найдите индекс элемента в отсортированном списке и вставьте его в другой список.

, поэтому такой метод, как

public List<Integer> giveSortIndexes(List<Integer> origList) {
    List<Integer> retValue = new ArrayList<Integer>();
    List<Integer> originalList = new ArrayList<Integer>(origList);
    Collections.sort(origList);
    Map<Integer, Integer> duplicates = new HashMap<Integer, Integer>();
    for (Integer i : originalList) {
        if(!duplicates.containsKey(i)) {
            retValue.add(origList.indexOf(i) + 1);
            duplicates.put(i, 1);
        } else {
            Integer currCount = duplicates.get(i);
            retValue.add(origList.indexOf(i) + 1 + currCount);
            duplicates.put(i, currCount + 1);
        }
    }
    return retValue;
}

Я не проверял коди может потребоваться дополнительная обработка для дубликатов.

Answer 3

Вот подход добавления индекса к каждому элементу, написанный в Scala. Этот подход имеет больше смысла.

list.zipWithIndex.sortBy{ case (elem, index) => elem }
  .map{ case (elem, index) => index }

В Java вам потребуется создать новый объект, который реализует совместимость.

class IndexedItem implements Comparable<IndexedItem> {
    int index;
    int item;

    public int compareTo(IndexItem other) {
        return this.item - other.item;
    }
}

Затем вы могли бы создать список IndexedItems, отсортировать его с помощью Collection.sort и затем извлечь индексы.

Вы также можете использовать Collections.sort в исходном списке с последующими вызовами indexOf.

for (int elem : originalList) {
    int index = newList.indexOf(elem);
    newList.get(index) = -1; // or some other value that won't be found in the list
    indices.add(index);
}

Это будет очень медленно (все проверки indexOf), но выполнит работу, если вам нужно будет сделать это только несколько раз.

Answer 4

Основываясь на том, что сказал Хури, я думаю, что самый простой способ сделать это - создать новый тип данных, который выглядит примерно так:

public class Foo {
    private Integer value;
    private int origPosition;
    private int sortedPosition;
    /*Constructors, getters, setters, etc... */
}

И некоторый псевдо-код для того, что делатьэто ...

private void printSortIndexes(ArrayList<Integer> integerList) {
    // Create an ArrayList<Foo> from integerList - O(n)
    // Iterate over the list setting the origPosition on each item - O(n)
    // Sort the list based on value
    // Iterate over the list setting the sortedPosition on each item - O(n)
    // Resort the list based on origPositon
    // Iterate over the lsit and print the sortedPositon - O(n)
}

Это не займет много времени для реализации, но это ужасно неэффективно.Вы добавляете дополнительные 4 O (n) операций, и каждый раз, когда вы добавляете или удаляете что-либо из своего списка, все позиции, хранящиеся в объектах, становятся недействительными - так что вам придется все пересоздавать.Кроме того, требуется, чтобы вы отсортировали список дважды.

Так что, если это небольшая проблема с набором данных небольшого размера, это будет работать, но если вы пытаетесь что-то использовать в течение длительного времени,Возможно, вы захотите придумать более элегантный способ сделать это.

Answer 5

Моя идея состоит в том, чтобы создать еще 1 индекс вызова атрибута помимо вашего значения (в каждом из данных aray). Он будет содержать ваш старый индекс, тогда вы можете взять его для использования.