以更好的方式在Java中找到double []數組中每個元素的等級

Question

我已經編寫了代碼來計算以下代碼中double []數組的每個元素的等級。舉個例子，如果我有double數組{3, 1.3, 2, 3}那麼我找到排名{2, 0, 1, 2}。據計算爲

• 1.3最少，因此有秩0
• 2是下一個，所以它得到了以秩1
• 3是下一個大數目，所以這兩個3的get等級2 。

public static void main() { 
    double[] x = {3, 1.3, 2, 3}; 
    System.out.println(Arrays.toString(x) + " - original"); 
    System.out.println("[2, 0, 1, 2] - should be"); 
    System.out.println(Arrays.toString(findRank(x)) + " - our rank"); 
} 

private static int[] findRank(double[] x){ 
    List<Double> lst = new ArrayList<Double>(); 
    int[] rank=new int[x.length]; // maximum length for already unique array 
    for(double d:x) 
     if (lst.indexOf(d) == -1) //only unique elements in list 
      lst.add(d); 

    Collections.sort(lst); 
    for(int i=0;i<x.length;i++) { 
     rank[i]=lst.indexOf(x[i]); 
    } 
    return rank; 
} 

此代碼給出以下輸出

[3.0, 1.3, 2.0, 3.0] - original 
[2, 0, 1, 2] - should be 
[2, 0, 1, 2] - our rank 

我感興趣的是上面代碼的更好實現。如何以更好的方式完成？

編輯

這個問題問重複的元素被類似地且連續地即{0,1,2,3,...}位列不跳過中間等級，這是從類似的，但不同的問題 How to find what is the rank of each element in an integer array不同。如果給出輸入{3,1,2,3}，那麼該問題需要輸出{3,0,1,3}。即它以不同的方式處理重複的元素，或者它在輸入中的重複值中斷。但是，這也是關於處理重複項，並且所需的輸出是{2,0,1,2}。

Answer 1

我會去的這種做法：

public static int[] findRank(double[] inp) { 
    int[] outp = new int[inp.length]; 
    for(int i = 0; i < inp.length; i++) { 
     for(int k = 0; k < inp.length; k++) { 
      if(inp[k] < inp[i]) outp[i]++; 
     } 
    } 
    return outp; 
} 

我只是這個來了個蒼蠅，所以我不能告訴100％，如果它是真的比你的方式快，但我會說這看起來更好，你不需要依賴於一般的Collections.sort()和Lists的java實現。

Answer 2

如果您正在尋找效率，請勿多次查找list.indexOf()列表的索引。在列表中查找元素的時間複雜度爲O（n），如http://infotechgems.blogspot.com/2011/11/java-collections-performance-time.html

解釋您可以使用Map而不是List。通過鍵Map查找元素使用O（1）複雜性。

Answer 3

假設排序是O（n log（n）），那麼單個O（n）過程將生成唯一的排序。使用lambda比較根據x []對整數I []進行排序（lambda比較需要I []爲Integer類型）。然後根據I []和x []生成唯一的秩R []。

// return unique rank 
private static int[] findRank(double[] x){ 
    int [] R = new int[x.length]; 
    if(x.length == 0)return R; 
    Integer [] I = new Integer[x.length]; 
    for(int i = 0; i < x.length; i++) 
     I[i] = i; 
    Arrays.sort(I, (i0, i1) -> (int) Math.signum(x[i0]-x[i1])); 
    int j = 0; 
    for(int i = 0; i < x.length; i++){ 
     if(x[I[i]] != x[I[j]]) 
      j = i; 
     R[I[i]] = j; 
    } 
    return R; 
} 

Answer 4

您的代碼中存在一些效率問題。首要的是使用array.indexOf()。在陣列中查找索引是昂貴的O（n）。您可以改爲創建一個Map來代替陣列，並使用x.get(key)來獲得與之相關的排名。您可以定義並在地圖中獲得的密鑰爲：

Map<Double,Integer> x = new HashMap<Double, Integer>(); 
x.put(3.5,0); 
x.put(2.0,1); 
x.put(4.1,2); 
//.... and put following in loop 
y=x.get(2.0); //y=1 

但HashMap使用雙作爲key可以做到的，但它可能不是很好的主意，因爲Double比較可能有浮點的問題。但基本的想法是使用O（1）成本。