Найдите общие элементы из двух списков (с PhoneNumberUtils.compare)

Question

Итак, в этом приложении для Android у меня есть два списка с номерами телефонов. Я хочу узнать общие числа в обоих. Метод грубой силы равен N^2. Я не могу использовать HashSets (я думаю), потому что числа могут быть в разных форматах. Поэтому лучше всего использовать PhoneNumberUtils.compare. (Он соответствует номерам разных форматов, например, возвращает true для «+91 9413294132» и «09413294132».

Я хочу эффективный способ, поскольку списки слишком велики. Я хочу узнать, какие номера зарегистрированы в моей базе данных (может быть, так же, как WhatsApp узнает, кто на WhatsApp). Я буду очень благодарен за любые усилия.

Answer 1

Это зависит от того,/время или оба из них.

1. Вы обеспокоены памяти

   Перейдите с грубой силой N решение, потому что оно не использует никакой дополнительной памяти вообще (только память, необходимая для хранения общих элементов), и N на практике не так уж плохо для небольших списков размеров. Во всяком случае, выбор телефонных номеров из базы данных, скорее всего, приведет к большему результату, чем ваш алгоритм N .

2. Вы беспокоитесь о времени, но вы можете использовать дополнительную память

   Оберните телефонные номера в класс-оболочку, и добавить все телефонные номера с 1-го списка на HashSet. Затем перейдите по второму списку и проверьте, содержит ли набор номер завернутого телефона или нет. Это гарантирует вам время O (m + k * n) (вам нужно перебирать каждый список только один раз, а метод HastSet содержит константу k - где k представляет среднее число строк, имеющих тот же hashCode.). Это имеет тенденцию к O (n), поскольку 2 и k (должно быть 1, поскольку столкновение hashSet() String довольно редко) являются постоянными факторами, которые можно отбросить.

   class PhoneNumber { 
   
       private final String val; 
   
       public PhoneNumber(final String val){ 
        this.val = val; 
       } 
   
       @Override 
       public int hashCode(){ 
        return this.getVal().hashCode(); 
       } 
   
       @Override 
       public boolean equals(Object obj){ 
        if (this == obj) { 
         return true; 
        } 
        if (obj == null) { 
         return false; 
        } 
        if (this.getClass() != obj.getClass()) { 
         return false; 
        } 
   
        PhoneNumber other = (PhoneNumber)obj; 
        return PhoneNumberUtils.compare(this.getVal(), other.getVal()) == 0; 
       } 
   
       public String getVal(){ 
        return this.val; 
       } 
   } 
   
   private Set<PhoneNumber> getCommonPhoneNumbers(List<String> dbPhoneNumbers , List<String> userPhoneNumbers){ 
       Set<PhoneNumber> common = new HashSet<PhoneNumber>(); 
   
       Set<PhoneNumber> phoneNumbers = new HashSet<PhoneNumber>(); 
       for(String s : userPhoneNumbers){ 
        phoneNumbers.add(new PhoneNumber(s)); 
       } 
   
       for(String s : dbPhoneNumbers){ 
        PhoneNumber phoneNo = new PhoneNumber(s); 
        if(phoneNumbers.contains(phoneNo)){ 
         common.add(phoneNo); 
        } 
       } 
   
       return common; 
   } 
   

3. Вы обеспокоены как памятью, так и временной сложностью.

   Сортировка 2 списков с использованием пользовательского компаратора на основе PhoneNumberUtils.compare(String,String) (это должно принимать O (n log n)), а затем перебирать оба списка сразу (O (min (m, n))):

   private static final Comparator<String> phoneNoComp = new Comparator<String>(){ 
        @Override 
        public int compare(final String s1, final String s2) { 
        return PhoneNumberUtils.compare(s1,s2); 
        } 
       }; 
   
       private Set<String> getCommonPhoneNumbers(final List<String> list1 , final List<String> list2){ 
   
        Set<String> common = new HashSet<String>(); 
   
        Collections.sort(list1, phoneNoComp); 
        Collections.sort(list2, phoneNoComp); 
   
        int size1 = list1.size(); 
        int size2 = list2.size(); 
        int i = 0, j = 0; 
   
        while(i < size1 && j < size2){ 
         int comparison = PhoneNumberUtils.compare(list1.get(i) , list2.get(j)); 
         if(comparison == 0) { // found a common element. 
          common.add(list1.get(i)); 
          i++; 
          j++; 
         } 
         else if(comparison == 1){ 
          j++; 
         } 
         else{ 
          i++; 
         } 
        } 
   
        return common; 
       }