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 List のオペレーター 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

リストを価格でソートしたことはないので、最低価格を期待するべきではありません。

一見すると、リストは国コード順にソートされています。

各国コード内の価格の順序は、次の両方に応じてランダムです。

  • 元のリストがソートされた不特定の順序...
  • 二分探索が正しい国コードで見つけた最初の値....

ロルフル

編集：

あなたは正しいアプローチがどうあるべきかを尋ねます.... 頭に浮かぶのは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)同じ countryCode の Dogs のリスト/コレクション/TreeSet を取得するために使用します。

次に、並べ替えO(nlogn)られていない場合は、Dog のコレクションを価格で並べ替え ()、(同等のインターフェイスを実装し、メソッドを実装する必要があります)、最初/最後の Dog を取得します。ソート順によって異なります。後で使用するためにコレクションをソートしておくこともできます。1回限りの仕事であれば、犬のコレクションを調べて、最低価格で犬を手に入れることもできます.O(n)

並べ替えも行う演算子が必要な場合は、その情報を compareTo メソッドの実装に書き込みます。

そして、あなたが言ったように、要素が数千しかない場合、最小/最大検索が何度も行われない限り、パフォーマンスをそれほど気にする必要はありません。その場合、マップを埋めるとき、またはあなたのアプローチでリストを作成する場合でも、countryCode の最小/最大価格の別のマップを作成します。これにより、後で多くの時間を節約できます。どうやら最小/最大価格をキャッシュする場合、マップ (またはリスト) が変更された場合、または一部の犬が変更された場合にそれを維持する必要があります。とにかく、あなたは自分の要件を最もよく知っているので、正しい道を選ぶことができます.

最後に、Java 命名規則について読んでください。CountryCode、Price は、フィールドではなくクラスのように見えます。

于 2013-01-23T23:11:53.627 に答える