降低产生秩数阵列的时间复杂度

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）的。