时间戳

首页 > 解决方案 > 找到满足特定条件的数组中当前位置右边的所有元素？

arrays - 找到满足特定条件的数组中当前位置右边的所有元素？

问题描述

假设我们当前的索引是并且我们有一个长度i数组。给我们的条件是来自哪里，并且对于每个有效位置，我们找到满足给定条件的对数的计数。arrnarr[i] > 2*arr[j]j[i+1,n-1]i [0<=i<n]

Constraints:
1 <= N <= 10^5 
1 <= arr[i] <= 10^9

Time Limit: 1sec

Sample Input 1:
10 = n
1 3 2 6 2 7 4 2 3 1 = arr
Sample Output 1:
9

Sample Input 2:
5 = n 
2 4 3 5 1 = arr
Sample Output 2:
3

所需的时间复杂度为 O(nlog n) ，有人可以建议我解决问题的有效方法吗？

标签： arraysalgorithmdata-structures

解决方案

您可以使用 Java 的 TreeMap 按如下方式解决此问题。

  • 遍历每个元素并将元素插入到树形图中（在幕后使用红黑树）并将元素出现的频率更新为值。
  • 现在查找键大于 2*current_element 的映射部分。
  • 获取地图部分中每个元素的频率并将其添加到您的结果中。

复杂度应该是 O(n*log(n)) 因为在 RB 树中的插入是 log(n) 并且寻找地图的一部分是 log(n) 并且你对每个元素都这样做。但是，如果您有很多重复项，情况可能会更糟。

Java中的代码是：

   private static int getCount(int[] a) {
     int count = 0;
     TreeMap<Integer, Integer> treeMap = new TreeMap<>();
     for ( int i = 0; i < a.length; i++ ) {
      
       if ( treeMap.containsKey(a[i])) {
         treeMap.put(a[i], treeMap.get(a[i]) + 1);
       } else {
         treeMap.put(a[i], 1);
       }
       NavigableMap<Integer, Integer> m = treeMap.tailMap(2*a[i], false);
       for ( Integer key : m.keySet() ) {
         count += m.get(key);
       }
     }
     return count;
  }

推荐阅读