时间戳

首页 > 解决方案 > 从第一个列表中查找最小元素

java - 从第一个列表中查找最小元素

问题描述

我有一个函数，它以 2 List 作为参数。我们想要的最终结果是从第一个列表中检查，有多少元素小于等于第二个列表中的每个元素？

例如：

firstlist = [1,4,2,4]
secondList = [3,5]

输出 = [2,4]解释
：
secondList[3] >= firstList[1,2] 所以总数是 2。 secondList[5] 是 >= firstList[1,4,2,4] 所以总数是 4。

我已经写了一个解决方案，但这不是优化的。

   public  List<Integer> counts(List<Integer> teamA, List<Integer> teamB) {
       // Write your code here
       int[] b = teamB.stream().mapToInt(i -> i).toArray();
       int[] a = teamA.stream().mapToInt(i -> i).toArray();
       int counter;
       List<Integer> goals = new ArrayList<>();
       for (int i= 0;i<b.length;i++){
           counter= 0;
           for (int j =0;j < a.length; j++){
               if (a[j] <= b[i]){
                   counter++;
               }
           }
           goals.add(counter);
       }
       return goals;

   }

标签： javaoptimizationjava-8

解决方案

如果你想降低时间复杂度，那么你可以对第一个列表进行排序，然后对第二个列表中的每个元素应用二分搜索来查找更少的数字。

这样，时间复杂度将从 降低O(N*M)到O(Mlog(N))

推荐阅读