小编Mok*_*rma的帖子

我正在做一个 hackerrank 问题，要求我找出使用插入排序对数组进行排序所需的移位次数，而无需实际使用插入排序对数组进行排序，因为否则时间复杂度将是 O(n^2)！这是我的超时代码。据我所知，调用 headSet 方法 n 次应该达到 O(n logn) 左右。

static class MyComp implements Comparator<Integer>{
    @Override
    public int compare(Integer o1, Integer o2) {
        return o1 <= o2 ? -1: 1;
    }
}



// Complete the insertionSort function below.
static int insertionSort(int[] arr) {

    SortedSet<Integer> set = new TreeSet<>(new MyComp());
    int count=0;
    for(int i=arr.length-1; i>=0;i--){
        set.add(arr[i]);
        int pos = set.headSet(arr[i]).size();
       // System.out.println(pos);
        if(pos>0){
            count=count+pos;
        }

    }

    return count;
}