查找未排序集合的不同元素的最大/最小值

Question

我有一个国家代码值列表(可以复制)和对应的价格，如Class Main中所示，我想用这种方式找到max/min：

如果国家代码= 0.1，我应该得到0.90，0.91，0.92的最大price= 0.92。以此类推，对于所有其他国家代码，即我想要找到每个不同国家代码的最高价格

我已经在下面显示的代码中成功地完成了这项工作。但是它非常慢，而且不是很好的方法。

我的方法:由于"Class Main“中的数据是相关的(国家代码，与价格)，我首先使用带有比较器的”电话“类按国家代码对数据进行排序，然后扫描”电话-数组列表“中的所有元素，然后通过比较ArrayList元素找到每个”不同的“国家代码的最大值。

class Telephone implements Comparator<Telephone>{
    private int countryCode; 
    private double price;

    Telephone(){
    }

    Telephone( int c, double p){
        countryCode= c;
        price= p;

    }

    public int getCountryCode(){
        return countryCode;
    }

    public double getPrice(){
        return price;
    }


    // Overriding the compare method to sort
    public int compare(Telephone d, Telephone d1){

        return d.getCountryCode() - d1.getCountryCode();    
    }

}


public class Main {                          
    /**                                     
    * @param args
    */
    public static void main(String[] args) {
        // Takes a list o Telephone objects
        ArrayList <Telephone> list = new ArrayList<Telephone>(); 
        ArrayList <Double> arr = new ArrayList<Double>(); 
        list.add(new Telephone(1, 0.9));
        list.add(new Telephone(268, 5.1 ));
        list.add(new Telephone(46, 0.17 ));
        list.add(new Telephone(46, 0.01));
        list.add(new Telephone(4631, 0.15 ));
        list.add(new Telephone(4620, 0.0 ));
        list.add(new Telephone(468, 0.15 ));
        list.add(new Telephone(46, 0.02));
        list.add(new Telephone(4673, 0.9));
        list.add(new Telephone(46732,1.1));



        list.add(new Telephone(1, 0.91 ));
        list.add(new Telephone(44, 0.4 ));
        list.add(new Telephone(92, 0.4 ));
        list.add(new Telephone(467, 0.2 ));
        list.add(new Telephone(4, 0.0001 ));

        list.add(new Telephone(1, 0.92 ));
        list.add(new Telephone(44, 0.5 ));

        list.add(new Telephone(467, 1.0 ));
        list.add(new Telephone(48, 1.2 ));
        list.add(new Telephone(4, 0.1));

        Collections.sort(list, new Telephone());

        for ( int i=0; i < list.size()-1; i++)
        {

            arr.clear();

            while ( list.get(i).getCountryCode()== list.get(i+1).getCountryCode())
            {

              arr.add(list.get(i).getPrice()) ;
              i=i+1;

            }
            arr.add(list.get(i).getPrice());

            arr.trimToSize();

            System.out.println( " Max value is " + Collections.max(arr).toString() + " for " +list.get(i).getCountryCode());
        }
    }   
}

Answer 1

你可以让Telephone实现Comparable，如果counrycodes相等，你可以在比较中计算你的价格。如果你对列表进行排序，你会先按控制代码排序，然后再按价格排序。

然后，您可以迭代您的电话集合，并保留每次交互的控制代码。您迭代的国家代码的最后一个元素将是价格最高的那个。这样，您可以一步完成国家代码比较和价格比较。

 public int compareTo(Telephone d){
    int cc1 = this.getCountryCode();
    int cc2 = d.getCountryCode();

    if(cc1 == cc2){
      double price1 = this.getPrice();
      double price2 = d.getPrice();          
      if(price1 < price2)
         return -1;
      if(price1 > price2)
         return 1;
      return 0;
    }

    return cc1 - cc2;    
 }

Answer 2

您可以在不预先进行任何排序的情况下做到这一点，因此您唯一的代价就是遍历集合的一次迭代和散列映射的插入时间。

Collection<Telephone> list = ...;

Map<Integer, Double> maximumPrices = new HashMap<Integer, Double>();

for(Telephone telephone : list) {
    Double checkPrice = maximumPrices.get(telephone.getCountryCode());
    if(checkPrice == null || checkPrice < telephone.getPrice()) {
        maximumPrices.put(telephone.getCountryCode(), telephone.getPrice());
    }
}

我将添加记录最低价格的支持留给您作为练习。

Answer 3

我认为最好的实现取决于你想要什么。

A)如果您有一组或多或少经常被呼叫的静态电话，您应该在添加新的电话时尝试设置最小和最大。

b)如果您经常添加telefons，则应仅在需要时才获取最小最大值。

对于a)，您可以使用HashMap，其中key是国家代码。

 HashMap<Integer,ArrayList<float>> telefonMap = new HashMap<Integer,ArrayList<float>();
 addtelephone(int coutrycode, float price ){
  if (telefonMap.contains(countrycode){
     telefonMap.get(contrycode).add(price);
     // if you have frequent min max requests add, else skip the next line
     Collections.sort(telefonMap.get(countrycode));
  }
  else {
     ArrayList<Float> tempList = new ArrayList<Float>();
     priceList.add(price);
     telefonMap.put(contrycode,tempList);
 }
}

现在您可以通过调用以下方法来获取min max元素

telephoneMap.get(countrycode).get(0 or telephoneMap.get(countrycode).size()-1)

如果您在添加电话时没有对数组进行排序，那么只需在此处调用数组并对其进行排序