迭代 Java 集合时最小化复杂性算法

Question

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

List<A> listofAElements

一个对象有 3 个字段 开始日期、结束日期 和 速率。需求正在此列表上进行迭代，每当我找到具有相同开始日期和结束日期的 2 个元素时，我应该只在列表中保留一个 rate = rate1 + rate2。

这是我为此所做的最简单的代码，但声纳对它的复杂性表示赞同：

    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） 时间复杂度。然后你迭代你的列表，把它们放到地图中，如果这样的元素已经存在，你只需将两者结合起来。

为了更好地理解，我将提供一个非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() );

Answer 2

我的想法是你的目标是什么（结合开始和结束日期相同的对象的速率），这可以通过基本的DP来实现。

只需存储每个最后的迭代并将其与当前迭代进行比较，如果您已经有类似的日期，则合并结果。

下面我分享我尝试过的例子。

ProductVo.Java

package com.stack;
import java.util.Date;
public class ProductVo {
    private Date startDate;
    private int rate;
    private Date endDate;
    public Date getStartDate() {
        return startDate;
    }
    public void setStartDate(Date startDate) {
        this.startDate = startDate;
    }
    public int getRate() {
        return rate;
    }
    public void setRate(int rate) {
        this.rate = rate;
    }
    public Date getEndDate() {
        return endDate;
    }
    public void setEndDate(Date endDate) {
        this.endDate = endDate;
    }
}

MainApp.Java

package com.stack;
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Date;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class MainApp {
    public static void main(String[] args) throws ParseException {
        // TODO Auto-generated method stub
        Map<Date, ProductVo> contains = new HashMap<>();
        List<ProductVo> list = new ArrayList<ProductVo>();
        ProductVo productVo1 = new ProductVo();
        productVo1.setStartDate(new SimpleDateFormat("dd/MM/yyyy").parse("01/10/2017"));
        productVo1.setEndDate(new SimpleDateFormat("dd/MM/yyyy").parse("02/10/2017"));
        productVo1.setRate(10);
        list.add(productVo1);
        ProductVo productVo2 = new ProductVo();
        productVo2.setStartDate(new SimpleDateFormat("dd/MM/yyyy").parse("04/10/2017"));
        productVo2.setEndDate(new SimpleDateFormat("dd/MM/yyyy").parse("04/10/2017"));
        productVo2.setRate(20);
        list.add(productVo2);
        ProductVo productVo3 = new ProductVo();
        productVo3.setStartDate(new SimpleDateFormat("dd/MM/yyyy").parse("01/10/2017"));
        productVo3.setEndDate(new SimpleDateFormat("dd/MM/yyyy").parse("02/10/2017"));
        productVo3.setRate(30);
        list.add(productVo3);
        list.forEach(v -> {
            if (contains.containsKey(v.getStartDate())) {
                ProductVo p = contains.get(v.getStartDate());
                if (p.getEndDate().equals(v.getEndDate())) {
                    System.out.println(v.getRate() + p.getRate());
                }
            }
            if (!contains.containsKey(v.getStartDate())) {
                contains.put(v.getStartDate(), v);
            }
        });
    }
}