java - 迭代 Java 集合时最小化复杂度算法

Question

我有一个场景，当我有一个对象列表让我们假设:

List<A> listofAElements

一个对象有 3 个字段 startDate、endDate 和 rate。需求在这个列表上迭代，每当我发现 2 个具有相同开始日期和结束日期的元素时，我应该只在列表中保留一个 rate = rate1 + rate2 的元素。

这是我为此所做的简单代码，但 Sonar 提示它的复杂性:

    public static void arrangeList(List<TauxPeriodesATDto> tauxPeriodesATDtos){

    for (int i =0 ; i < tauxPeriodesATDtos.size() ; i++  ){

        for (int j = tauxPeriodesATDtos.size() -1 ; j >= 0; j-- ){

            if (j != i){
                    boolean isStartDatesEquals = tauxPeriodesATDtos.get(i).getDateDebut().equals(tauxPeriodesATDtos.get(j).getDateDebut());
                    boolean isEndDatesEquals = tauxPeriodesATDtos.get(i).getDateFin().equals(tauxPeriodesATDtos.get(j).getDateFin());

                    if (isStartDatesEquals && isEndDatesEquals ) {
                        BigDecimal itauxPrime = tauxPeriodesATDtos.get(i).getTauxPrimeAT();
                        BigDecimal jTauxPrime = tauxPeriodesATDtos.get(j).getTauxPrimeAT();
                        BigDecimal sommeDesTaux = itauxPrime.add(jTauxPrime);
                        tauxPeriodesATDtos.get(i).setTauxPrimeAT(sommeDesTaux);
                        tauxPeriodesATDtos.remove(j);
                    }

            }

        }

    }
}

对于更好的方法，您有什么建议吗？

Answer 1

如果您使用 LinkedHashMap，其键是由开始日期和结束日期组成的周期，其值是元素，您应该能够获得 O(n) 时间复杂度。然后你遍历你的列表，将它们放入 map 中，如果这样的元素已经存在，你只需将两者结合起来。

为了更好地理解，我将提供一个非 lambda/流式版本:

//Pair is org.apache.commons.lang3.tuple.Pair, you could also provide your own class
Map<Pair<Date, Date>, TauxPeriodesATDto> combined = new LinkedHashMap<>();

for( TauxPeriodesATDto element : tauxPeriodesATDtos ) {
  Pair<Date, Date> key = Pair.of( element.getDateDebut(), element.getDateFin() );
  TauxPeriodesATDto existing = combined.get( key );

  if( existing != null ) {
    //duplicate already exists, so combine the two
    existing.setTauxPrimeAT( existing.getTauxPrimeAT().add( element.getTauxPrimeAT() );
  } else {
    //no duplicate yet
    combined.put( key, element );
  }      
}

//due to the use of LinkedHashMap the order of elements should be preserved
List<TauxPeriodesATDto> resultList = new ArrayList<>( combined.values() );

Java8 变体可能如下所示:

LinkedHashMap<Pair, Element> combined = tauxPeriodesATDtos.stream().collect( 
       Collectors.toMap( (element) -> Pair.of( element.getDateDebut(), element.getDateFin()), //create the key
                         Function.identity(), //just use the new element
                         (e,n) -> { e.setTauxPrimeAT( e.getTauxPrimeAT().add( n.getTauxPrimeAT() ); return e; }, //combine the elements and return the existing one
                         LinkedHashMap::new ) ); //use a LinkedHashMap

List<TauxPeriodesATDto> resultList = new ArrayList<>( combined.values() );