降低產生秩數陣列的時間複雜度

Question

public Ranking（String [] names，float [] scores）{ nameTest = new Cities [names.length]; rankTest = new Cities [names.length]; city = new Cities [names.length]; scoreRanks = new Float [scores.length];對於（int i = 0; i < scores.length - 1; i ++）{ if（scores [i] == scores [i + 1]） throw new IllegalArgumentException（）; } if（names == null || scores == null） throw new NullPointerException（）; if（names.length！= scores.length） throw new IllegalArgumentException（）;

 for (int p = 0; p < scoreRanks.length; p++) { 
      scoreRanks[p] = scores[p]; 
     } 
     int[] ranking = new int[names.length]; 
     for (int k = 0; k < ranking.length; k++) { 
      ranking[this.smallestIndex()] = k + 1; 
     } 
     for (int i = 0; i < ranking.length; i++) { 
      city[i] = new Cities(names[i], ranking[i]); 
      nameTest[i] = new Cities(names[i], ranking[i]); 
      rankTest[i] = new Cities(names[i], ranking[i]); 
     } 
     Arrays.sort(nameTest, Cities.BY_NAME); 
     Arrays.sort(rankTest, Cities.BY_RANK); 
     for (int i = 0; i < names.length - 1; i++) { 
      if (nameTest[i].getName().equals(nameTest[i + 1].getName()) 
        || nameTest[i].getName() == null 
        || rankTest[i].getRank() == rankTest[i + 1].getRank()) 
       throw new IllegalArgumentException(); 
     } 
    } 

    public int smallestIndex() { 
     float smallest = 0.0f; 
     int i; 
     for (i = 0; i < scoreRanks.length; i++) { 
      if (scoreRanks[i] > 0.0f) { 
       smallest = scoreRanks[i]; 
       break; 
      } else 
       continue; 
     } 
     int j = 1; 
     while (j < scoreRanks.length) { 
      if (scoreRanks[j] < smallest && scoreRanks[j] != 0.0f) { 
       smallest = scoreRanks[j]; 
       i = j; 
      } 
      j++; 
     } 
     scoreRanks[i] = 0.0f; 
     return i; 
    } 

這是我的排名構造函數。目前，for循環內的smallestIndex（）調用會將其調高到O（n^2）時間，但我需要它在不超過O（n log n）時間內運行。

這是做什麼是一個分數和名稱的數組。然後，LOWEST分數爲1，次低爲2，依此類推。然後，我可以創建名稱[i]與排名[i]相對應的城市對象。

希望是有道理的。買耶我沒有得到我能做的，以獲得相同的結果，但在O（n日誌n）時間。我的代碼完美的作品，它實在是太慢了我想:(。

另外，將O（2N日誌N + 5N）歸結爲爲O（n log n）的？

Answer 1

從你的描述，基本上你想要根據不斷提高的分數對列表進行排序，在smallestIndex中檢查代碼，似乎確實是以非常低效的方式來做到這一點，如果要保留該方法，我建議將scoreRanks[i] = 0.0f更改爲scoreRanks[i] = Float.MAX_VALUE，並簡化方法。只是循環一次

但爲了有效地完成您的任務，我建議完全刪除smallestIndex我看到您已經在使用Arrays.sort與cu stom比較器。只需使用相同的方法即可高效地解決您的任務。您可以創建自定義的比較在這個問題解釋說：Get the indices of an array after sorting?

class ArrayIndexComparator implements Comparator<Integer> 
{ 
    private Float[] scores; 

    public ArrayIndexComparator(float[] scores) 
    { 
     this.scores = new Float[scores.length]; 
     for(int i=0; i<scores.length; i++){ 
      this.scores[i] = scores[i]; 
     } 
    } 

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

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

    public static void main(String[] args){ 
     float[] scoreRanks = new float[]{2.0f,3.0f,1.0f}; 
     ArrayIndexComparator comparator = new ArrayIndexComparator(scoreRanks); 
     Integer[] indexes = comparator.createIndexArray(); 
     Arrays.sort(indexes, comparator); 
     int[] ranking = new int[indexes.length]; 
     for (int i = 0; i < ranking.length; i++) { 
      ranking[indexes[i]] = i + 1; 
     } 
     for (int i = 0; i < ranking.length; i++){ 
      System.out.println(ranking[i]+" "+scoreRanks[i]); 
     } 
     // Will print: 
     // 2.0 2 
     // 3.0 3 
     // 1.0 1 
    } 
} 

public Ranking(String[] names, float[] scores) { 
    nameTest = new Cities[names.length]; 
    rankTest = new Cities[names.length]; 
    city = new Cities[names.length]; 
    scoreRanks = new Float[scores.length]; 
    for (int i = 0; i < scores.length - 1; i++) { 
     if (scores[i] == scores[i + 1]) 
      throw new IllegalArgumentException(); 
    } 
    if (names == null || scores == null) 
     throw new NullPointerException(); 
    if (names.length != scores.length) 
     throw new IllegalArgumentException(); 
    for (int p = 0; p < scoreRanks.length; p++) { 
     scoreRanks[p] = scores[p]; 
    } 
    // This is the updated part 
    ArrayIndexComparator comparator = new ArrayIndexComparator(scoreRanks); 
    Integer[] indexes = comparator.createIndexArray(); 
    Arrays.sort(indexes, comparator); 
    int[] ranking = new int[indexes.length]; 
    for (int i = 0; i < ranking.length; i++) { 
     ranking[indexes[i]] = i + 1; 
    } 
    // Up until this part 
    for (int i = 0; i < ranking.length; i++) { 
     city[i] = new Cities(names[i], ranking[i]); 
     nameTest[i] = new Cities(names[i], ranking[i]); 
     rankTest[i] = new Cities(names[i], ranking[i]); 
    } 
    Arrays.sort(nameTest, Cities.BY_NAME); 
    Arrays.sort(rankTest, Cities.BY_RANK); 
    for (int i = 0; i < names.length - 1; i++) { 
     if (nameTest[i].getName().equals(nameTest[i + 1].getName()) 
       || nameTest[i].getName() == null 
       || rankTest[i].getRank() == rankTest[i + 1].getRank()) 
      throw new IllegalArgumentException(); 
    } 
} 

這樣，您將使用排序方法Arrays類，這是O（n log n）的。