0 
Country Code List=   92,  445,  445,  966,   92,  445,  966,  966, 92
Price List =       0.99, 0.91, 0.92, 0.97, 0.93, 0.97, 0.92, 0.97, 1.0
Operator List=        A,    C,    A,    B,    C,    B,    A,    C,  A

当用户输入国家代码时，我应该找到最低价目表和相应的运营商。国家代码数据可以复制。它不是唯一的。例如，由于我们不知道 countrycode：92 属于哪个运营商，因此在 countrycode 列表中，运营商 A、B 或 C 可以存在 92。

我已经写了下面的代码。但它有一个问题，

问题：我可以对 CountryCode 进行排序，但以下代码中的 binarySearch 无法找到相应的最低价目表。它总是给我随机值，这不是最低价格。对以下代码的改进将不胜感激。

class Dog implements Comparator<Dog>, Comparable<Dog>{
   private int CountryCode; 
   private double Price;
   private String Operator;
   Dog(){
   }

   Dog( int c, double p, String o){
       CountryCode= c;
       Price= p;
       Operator=o;
   }

   public int getCountryCode(){
      return CountryCode;
   }

   public double getPrice(){
      return Price;
   }
   public String getOperator(){
          return Operator;
       }


   // Overriding the compareTo method
   public int compareTo(Dog d){

       return CountryCode- d.getCountryCode();
   }


   // Overriding the compare method to sort the age 
   public int compare(Dog d, Dog d1){
       return d.CountryCode - d1.CountryCode;     
   }




}


public class Ser {                          
/**                                     
 * @param args
 */
public static void main(String[] args) {
    // Takes a list o Dog objects
    ArrayList <Dog> list1 = new ArrayList<Dog>();

      list1.add(new Dog(92, 0.99 , "A"));
      list1.add(new Dog(445, 0.91 , "C"));
      list1.add(new Dog(445, 0.92 , "A"));
      list1.add(new Dog(966, 0.97 , "B"));
      list1.add(new Dog(92, 0.93 , "C"));
      list1.add(new Dog(445, 0.97 , "B"));
      list1.add(new Dog(966, 0.92, "A"));
      list1.add(new Dog(966,0.97, "C"));
      list1.add(new Dog(92,1.0, "A"));
      // Sorts the array list using comparator

      Collections.sort(list1, new Dog());

      for(Dog a: list1)//printing the sorted list of ages
          System.out.println(a.getCountryCode() +"  : "+
         a.getOperator()+"  : "+ a.getPrice());

     int index=  Collections.binarySearch(list1, new Dog ( 92,null,null));

      if (index>=0)
      System.out.println( list1.get(index).getOperator()+ " " + list1.get(index).getPrice());
      else
          System.out.println("No operator is availible");

}}
4

2 回答 2

3

您从未按价格对列表进行排序，因此您不应期望获得最低价格。

乍一看，列表是按国家代码排序的。

每个国家代码中的价格顺序是随机的，取决于两者：

  • 原始列表排序的未指定顺序...
  • 使用正确的国家代码进行二分搜索找到的第一个值....

滚滚

编辑：

你问正确的方法应该是什么......我想到了三个：

  • 使用 Kent 对预先构建的层次结构的建议，该结构对两个维度（国家/价格）上的数据进行排序，然后您可以快速提取所需的数据。
  • 将比较器更改为按国家和价格排序，然后扫描列表（而不是二分搜索），并返回具有正确国家/地区的第一项。
  • 将比较器更改为按国家和价格排序，然后使用二分搜索来搜索该国家（二分搜索将返回具有该国家/地区的任何位置），然后向后扫描以找到最低价格。
于 2013-01-23T23:06:19.360 回答
1

如果您的要求是：if find multiple Dogs with same countryCode, return the Dog with lowest price.

我建议你改变你的列表设计。

你可以有一个Map<Integer, List<Dog>>关键是countryCode。当然，Map<Integer, TreeSet<Dog>>或者番石榴MultiMap<Integer, Dog>也可以。

如果countryCodes是真正的国家，您的地图将不会有超过 300 个条目。

然后您可以保存该O(logn)二进制搜索。并用于O(1)获取相同国家代码的 Dogs 列表/集合/TreeSet。

然后，O(nlogn)如果未排序，您可以按价格对 Dog 的集合进行排序（）。（您应该实现可比较的接口并实现方法）并获取第一个/最后一个 Dog。取决于你的排序顺序。您还可以对集合进行排序以供以后使用。如果只是一次性工作，你甚至可以通过 Dog collection 以最低的价格获得 Dog。O(n)

如果您也想让运算符进行排序，请将该信息写入您的 compareTo 方法实现。

如果像你说的那样，只有几千个元素，你不必太在意性能，除非最小/最大搜索会进行很多次。如果在这种情况下，当您填写地图时，或者即使使用您的方法，列表，为国家代码的最低/最高价格构建另一张地图。这将在以后节省大量时间。显然，如果您缓存最低/最高价格，如果地图（或您的列表）被更改，或者某些狗被修改，您必须维护它。无论如何，您最了解您的需求，您可以选择正确的方式。

最后，请阅读一些有关 java 命名约定的内容。CountryCode、Price 看起来像 Class 而不是字段。

于 2013-01-23T23:11:53.627 回答