Java中與索引相關的排序問題

Question

這是我在找到解決方案時遇到問題的要求。

問題：

我的ArrayList與數據20，10，30，50，40，10，

如果我們以升序進行排序這樣做的結果將是10,10 ，20，30，40，50.

但我需要的結果爲3,1,4,6,5,2。（排序後每個元素的索引）。

嚴格來說，即使列表中有重複元素，也應該可以工作。

請分享你的想法/方法解決這個問題。

Answer 1

我的想法是在你的價值旁邊（在aray的每個數據中）創建另外1個屬性調用索引。它會保存你的舊索引，然後你可以拿出來使用它。

Answer 2

以下是在Scala中寫出的每個元素中添加索引的方法。這種方法最有意義。

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

在Java中，你需要創建一個實現comperable一個新的對象。

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 3

建設關什麼Hury說，我覺得我可以看到這樣做的最簡單的方法是使看起來像一個新的數據類型：

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 4

一個簡單的方法是排序列表;然後在原始列表上循環，找到排序列表中元素的索引並將其插入到另一個列表中。

所以像

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 5

這裏是我的解決方案。我們定義一個比較器，根據列表中的相應對象對索引列表進行排序。這使我們的索引列表，實際上是一個地圖：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); 


    } 


}