使用比較器在ArrayList中搜索

Question

今天我接受了一次採訪，我已經給出了兩個java類，並要求通過註冊號搜索狗的詳細信息。我知道Java.util.ArrayList.contains(Object)，但不知道如何實現有多個字段時。

第二個問題是：在這個例子中可以使用的最有效的搜索技術是什麼？我想過Collections.binarySearch，但不確定它在這個例子中是最有效的。如果是這樣，我該如何執行它？

DogSort.java

public class DogSort { 

public static void main(String[] args) { 
    ArrayList<Dog> listDog = new ArrayList<Dog>(); 

    Scanner sc = new Scanner(System.in); 

    listDog.add(new Dog("Max", "German Shepherd", "33")); 
    listDog.add(new Dog("Gracie","Rottweiler","11")); 
    Collections.sort(listDog, Dog.COMPARE_BY_NAME); 
       System.out.println(listDog); 
    } 
} 

Dog.java

class Dog { 
    private String name; 
    private String breed; 
    private String registrationNumber; 

public Dog(String name, String breed, String registrationNumber) { 
     this.name = name; 
     this.breed = breed; 
     this.registrationNumber = registrationNumber; 
    } 

public static Comparator<Dog> COMPARE_BY_NAME = new Comparator<Dog>() { 
     public int compare(Dog one, Dog other) { 
      return one.name.compareTo(other.name); 
     } 
}; 
//getter and setter methods for all private variable 

} 

Answer 1

它註冊加入一個HashMap的Key和Dog對象的值，然後搜索Map。

O(1)插入和O(1)搜索。

二進制搜索O(log n)。

Answer 2

我同意@Pritam Banerjee的回答。最有效的搜索技術是在這種情況下使用HashMap。我會建議使用HashSet，但HashSet＃包含方法返回布爾值，所以只需使用map。這是代碼片段。

只是爲了信息當使用基於散列的集合/地圖，不要忘記來實現的hashCode妥善equals方法。

public class DogSearch { 
    public static void main(String[] args) { 
     Map<String, Dog> dogs = new HashMap<String, Dog>(); 

     Dog max = new Dog("Max", "German Shepherd", "1001"); 
     Dog gracie = new Dog("Gracie", "Rottweiler", "1002"); 
     Dog luca = new Dog("Luca", "Labrador", "1003"); 
     Dog tiger = new Dog("Tiger", "Beagle", "1004"); 
     Dog meemo = new Dog("Meemo", "Bulldog", "1005"); 
     Dog lacie = new Dog("Lacie", "German Shorthaired Pointer", "1006"); 

     dogs.put(max.getRegistrationNumber(), max); 
     dogs.put(gracie.getRegistrationNumber(), gracie); 
     dogs.put(luca.getRegistrationNumber(), luca); 
     dogs.put(tiger.getRegistrationNumber(), tiger); 
     dogs.put(meemo.getRegistrationNumber(), meemo); 
     dogs.put(lacie.getRegistrationNumber(), lacie); 

     Dog result = dogs.get("1002"); 

     if (result == null) { 
      System.out.println("Dog not found"); 
     } else { 
      System.out.println(result); 
     } 
    } 
} 

class Dog { 
    private String name; 
    private String breed; 
    private String registrationNumber; 

    public Dog(String name, String breed, String registrationNumber) { 
     this.name = name; 
     this.breed = breed; 
     this.registrationNumber = registrationNumber; 
    } 

    public static Comparator<Dog> COMPARE_BY_NAME = new Comparator<Dog>() { 
     public int compare(Dog one, Dog other) { 
      return one.name.compareTo(other.name); 
     } 
    }; 

    public String getName() { 
     return name; 
    } 

    public void setName(String name) { 
     this.name = name; 
    } 

    public String getBreed() { 
     return breed; 
    } 

    public void setBreed(String breed) { 
     this.breed = breed; 
    } 

    public String getRegistrationNumber() { 
     return registrationNumber; 
    } 

    public void setRegistrationNumber(String registrationNumber) { 
     this.registrationNumber = registrationNumber; 
    } 

    @Override 
    public int hashCode() { 
     final int prime = 31; 
     int result = 1; 
     result = prime * result + ((breed == null) ? 0 : breed.hashCode()); 
     result = prime * result + ((name == null) ? 0 : name.hashCode()); 
     result = prime * result + ((registrationNumber == null) ? 0 : registrationNumber.hashCode()); 
     return result; 
    } 

    @Override 
    public boolean equals(Object obj) { 
     if (this == obj) 
      return true; 
     if (obj == null) 
      return false; 
     if (getClass() != obj.getClass()) 
      return false; 
     Dog other = (Dog) obj; 
     if (breed == null) { 
      if (other.breed != null) 
       return false; 
     } else if (!breed.equals(other.breed)) 
      return false; 
     if (name == null) { 
      if (other.name != null) 
       return false; 
     } else if (!name.equals(other.name)) 
      return false; 
     if (registrationNumber == null) { 
      if (other.registrationNumber != null) 
       return false; 
     } else if (!registrationNumber.equals(other.registrationNumber)) 
      return false; 
     return true; 
    } 

    @Override 
    public String toString() { 
     return "Dog [name=" + name + ", breed=" + breed + ", registrationNumber=" + registrationNumber + "]"; 
    } 

} 

時間複雜度

插入：O（1）

搜索：O（1）

Answer 3

對於第一個問題，即通過註冊號此處搜索細節代碼

import java.util.Comparator; 
import java.util.TreeMap; 

public class DogSort { 

    public static void main(String[] args) { 
     TreeMap<Integer, Dog> listDogs = new TreeMap<>(); 
     listDogs.put(33, new Dog("Max", "German Shepherd", "33")); 
     listDogs.put(11, new Dog("Gracie", "Rottweiler", "11")); 
     System.out.println(listDogs); 
     System.out.println(listDogs.containsKey(11)); 
     System.out.println(listDogs.get(11)); 
    } 
} 

class Dog { 
    private String name; 
    private String breed; 
    private String registrationNumber; 

    public Dog(String name, String breed, String registrationNumber) { 
     this.name = name; 
     this.breed = breed; 
     this.registrationNumber = registrationNumber; 
    } 

    public static Comparator<Dog> COMPARE_BY_NAME = new Comparator<Dog>() { 
     public int compare(Dog one, Dog other) { 
      return one.name.compareTo(other.name); 
     } 
    }; 

    @Override 
    public String toString() { 
     return "Dog [name=" + name + ", breed=" + breed + ", registrationNumber=" + registrationNumber + "]"; 
    } 

} 

使用arraylist得到登錄號碼的狗的詳細是非常困難的，但是與地圖相當容易。

而且你可以重寫hashcode和equals方法，但是arraylist比較方法的工作方式不同。

你可以做的是你可以寫一個方法，可以通過註冊號查詢詳細信息。該方法必須迭代列表並找到Dog對象，並且如果列表已排序，則需要實現自己的二進制搜索以根據註冊號獲取Dog對象。

import java.util.ArrayList; 
import java.util.Collections; 
import java.util.Comparator; 

public class DogSort { 

    public static void main(String[] args) { 
     ArrayList<Dog> listDog = new ArrayList<Dog>(); 

     listDog.add(new Dog("Max", "German Shepherd", "33")); 
     listDog.add(new Dog("Gracie", "Rottweiler", "11")); 

     Collections.sort(listDog, Dog.COMPARE_BY_NAME); 

     System.out.println(listDog); 
     System.out.println(listDog.contains(new Dog("Max", "Rottweiler", "33"))); 
    } 
} 

class Dog { 
    private String name; 
    private String breed; 
    private String registrationNumber; 

    public Dog(String name, String breed, String registrationNumber) { 
     this.name = name; 
     this.breed = breed; 
     this.registrationNumber = registrationNumber; 
    } 

    public static Comparator<Dog> COMPARE_BY_NAME = new Comparator<Dog>() { 
     public int compare(Dog one, Dog other) { 
      return one.name.compareTo(other.name); 
     } 
    }; 

    @Override 
    public String toString() { 
     return "Dog [name=" + name + "]"; 
    } 

    @Override 
    public int hashCode() { 
     final int prime = 31; 
     int result = 1; 
     result = prime * result + ((registrationNumber == null) ? 0 : registrationNumber.hashCode()); 
     return result; 
    } 

    @Override 
    public boolean equals(Object obj) { 
     if (this == obj) 
      return true; 
     if (obj == null) 
      return false; 
     if (getClass() != obj.getClass()) 
      return false; 
     Dog other = (Dog) obj; 
     if (registrationNumber == null) { 
      if (other.registrationNumber != null) 
       return false; 
     } else if (!registrationNumber.equals(other.registrationNumber)) 
      return false; 
     return true; 
    } 


}