java - 在运行时间 O(n logn) 内比较数组的每个元素

Question

我必须检查每个元素是否有任何元素大于数组中的元素。这意味着，数组必须按降序排序。如果存在任何大于当前元素的元素，那么我会计算数组中存在多少个大于我正在检查的当前元素的数字。这样，我必须检查每个元素。我的输出必须是元素大于当前元素的总次数(考虑数组的每个元素)。

问题是我必须在 O(n logn) 内完成。我可以用简单的方式做到这一点，但运行时间是 O(n^2)。

public class CountPairs {
       public static int countPairs(int[] arr) {
           int Pairs=0;
           for (int i=0;i<arr.length;i++){
               for (int j=i+1;j<arr.length;j++){
                    if (arr[i] < arr[j]){
                         Pairs++;
                    }
               }
           }
           return Pairs;
      }
   }

例如:System.out.println(countPairs({3,1,4,2}) 应返回 3。请帮我解决这个问题。

Answer 1

假设你的数组确实已排序，你可以用二分搜索替换内部循环。请参阅 java.util.Arrays#binarySearch。

如果你不确定你的数组是否真的排序，你可以在线性时间内检查它:如果元素 i+1 大于元素 i，则数组不按降序排序。那时你可以使用 Arrays #sort 在 O(n log(n)) 中对数组进行排序。