Удалить дубликат в ArrayList пользовательских объектов

Question

Я пытаюсь удалить повторяющиеся объекты из моего массива.

У меня есть мой обычай, который состоит из двух двойных: x и y.

Что я хочу сделать, это удалить дубликаты ((х & & у) == (x1 & & y1)) и если х == x1 я хочу сохранить объект, который имеет более высокий у.

ArrayList<MyObject> list = [x(0),y(0)], [x(0),y(0)], [x(0.5),y(0.5], [x(0.5),y(0.6)], [x(1),y(1)]; 
ArrayList<MyObject> results = [x(0),y(0)], [x(0.5),y(0.6)], [x(1),y(1)]; 

Я попытался реализовать метод Equals, но я не знаю, как использовать его:

public boolean equals(Object obj) { 
    if (obj == null || !(obj instanceof MyObject)) { 
     return false; 
    } 
    return (this.x == ((MyObject)obj).x); 
} 

список всегда заказать с помощью Collections.sort х.

Спасибо за все.

Answer 1

Учитывая MyObject так:

class MyObject { 
    private final double x; 
    private final double y; 

    public MyObject(double x, double y) { 
     this.x = x; 
     this.y = y; 
    } 

    @Override 
    public boolean equals(Object o) { 
     if (this == o) return true; 
     if (o == null || getClass() != o.getClass()) return false; 

     MyObject myObject = (MyObject) o; 

     if (Double.compare(myObject.x, x) != 0) return false; 
     if (Double.compare(myObject.y, y) != 0) return false; 

     return true; 
    } 

    @Override 
    public int hashCode() { 
     int result; 
     long temp; 
     temp = Double.doubleToLongBits(x); 
     result = (int) (temp^(temp >>> 32)); 
     temp = Double.doubleToLongBits(y); 
     result = 31 * result + (int) (temp^(temp >>> 32)); 
     return result; 
    } 
} 

Вы можете реализовать unique метод, который возвращает список только с уникальными элементами:

private List<MyObject> unique(List<MyObject> list) { 
    List<MyObject> uniqueList = new ArrayList<>(); 
    Set<MyObject> uniqueSet = new HashSet<>(); 
    for (MyObject obj : list) { 
     if (uniqueSet.add(obj)) { 
      uniqueList.add(obj); 
     } 
    } 
    return uniqueList; 
} 

и тест блока для того, чтобы проверить это работает:

@Test 
public void removeDups() { 
    List<MyObject> list = Arrays.asList(new MyObject(0, 0), new MyObject(0, 0), new MyObject(0.5, 0.5), new MyObject(0.5, 0.6), new MyObject(1, 1)); 
    List<MyObject> results = Arrays.asList(new MyObject(0, 0), new MyObject(0.5, 0.5), new MyObject(0.5, 0.6), new MyObject(1, 1)); 
    assertEquals(results, unique(list)); 
} 

Примечание: важно реализовать как equals и hashCode для этого, из-за использования хэш-карты. Но вы всегда должны делать это в своих пользовательских классах: предоставить соответствующие версии equals и hashCode. Кстати, я не писал эти методы equals и hashCode. Я позволяю своей среде IDE (IntelliJ) генерировать их автоматически из полей x и y класса.

Answer 2

Обязательно переопределите метод equals() в вашем пользовательском объекте (MyObject).

Затем добавьте их в Set. Теперь у вас есть уникальный результирующий набор.

Answer 3

Используйте Set вместо List ...

Вы должны переопределить equals() и hashCode(). Большинство IDE могут генерировать это для вас!

Чтобы «преобразовать» список в набор, вы можете просто использовать это:

ArrayList<MyObject> list = ... 
Set<MyObject> mySet = new HashSet<MyObject>(list); 

Тогда у вас есть набор с уникальными элементами. Вы можете перемещаться по множеству, как это:

for (MyObject o : mySet){ 
    o.getX(); 
} 

Answer 4

Вы должны заказать свою коллекцию как на x и y с x первым (думаю о нем, как х и у формирования гипотетического числа с х в левой части десятичной точки и y с правой стороны: при сортировке числа в порядке возрастания, если составные части равны, вы сортируете десятичную часть). Теперь, с предикатом equal, будет сложно сортировать значения (вы можете только сказать, равны ли они, а не если они находятся перед другим). Вместо этого, вы должны реализовать интерфейс comparable со следующим методом:

public int compare(Object obj) { 
    if (obj == null || !(obj instanceof MyObject)) { 
    // raise an Exception 
    } 
    MyObject other = (MyObject)obj; 
    if (x < other.x) return -1; 
if (this.x > other.x) return 1; 
    if (this.y < other.y) return -1; 
    if (this.y > other.y) return 1; 
    return 0; 
} 

Если массив отсортирован в соответствии с этим сравнением, нужно просто сохранить последнюю запись с таким же x в массиве, чтобы получить то, что вы хотите. Это означает, что вы удаляете записи , если только у его преемника нет x.

Этот метод интересен тем, что вы не хотите хранить исходные данные, но сохраняете результат: он обновит существующий массив на месте, для сложности O (n) во времени (не считая сортировка, которая должна произойти в любом случае, если я правильно понимаю ваш вопрос).

---

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

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

Наконец, этот алгоритм может быть адаптирован к обновлению исходного массива на месте. Это немного сложнее, но позволит вам избежать дополнительного распределения (что важно для встроенных систем).

Псевдо код:

int idx = 0; 
while (idx + 1 < Objarray.size()){ 
    MyObj oi = Objarray.get(idx), on = Objarray.get(idx+1); 
    if (oi.x == on.x) { 
    if (on.y < oi.y) 
     Objarray.remove(idx++); 
    else 
     Objarray.remove(idx+1); 
    } else 
    idx++; 
} 

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

Answer 5

Наиболее оптимальным решением было бы, если бы вы могли использовать Set. Однако в Java реализованы две версии Set: HashSet и TreeSet. HashSet требует, чтобы вы объявили equals и hashCode способами, в то время как TreeSet требует, чтобы ваш класс реализовал Comparable с помощью метода compareTo или поставил Comparator. Ни одно решение не будет работать в вашем случае, потому что вы хотите сохранить выше y, когда x равно.Если вы сортируете/вычисляете равенство, основанное на x, y, у вас будет дубликат x, и если вы сортируете/вычисляете равенство на основе x, вы получите только первый введенный x, что не то, что вы хотите.

Поэтому то, что нам нужно сделать, это:

1. Сортировать по х по возрастанию, у убыванию
2. Преобразовать в Set, сохраняющим первоначальный порядок, но основы равенства только на x
3. Преобразовать обратно в список (при необходимости)

XAscYdesc Компаратор Метод (Без учета нулям):

public int compare(MyObject left, MyObject right) { 
    int c = left.x - right.x; 
    if(c != 0) { 
    return c; 
    } 
    return right.y - left.y; 
} 

XAsc Компаратор Метод (Без учета нулям):

public int compare(MyObject left, MyObject right) { 
    return left.x - right.x; 
} 

(Использование библиотеки Guava; это очень полезно для острот, как это):

Collections.sort(list, new XAscYdesc()); 
Lists.newArrayList(ImmutableSortedSet.copyOf(new XAsc(), list)); 

Answer 6

/** 
* 
*/ 
package test1; 

import java.util.ArrayList; 
import java.util.HashSet; 
import java.util.List; 
import java.util.Set; 

/** 
* @author raviteja 
* 
*/ 
public class UinquecutomObjects { 

    /** 
    * @param args 
    */ 
    public static void main(String[] args) { 
     // TODO Auto-generated method stub 
     Employee e1=new Employee(); 
     e1.setName("abc"); 
     e1.setNo(1); 

     Employee e2=new Employee(); 
     e2.setName("def"); 
     e2.setNo(2); 

     Employee e3=new Employee(); 
     e3.setName("abc"); 
     e3.setNo(1); 

     List<Employee> empList=new ArrayList<Employee>(); 
     empList.add(e1); 
     empList.add(e2); 
     empList.add(e3); 

     System.out.println("list size is "+empList.size()); 

     Set<Employee> set=new HashSet<Employee>(empList); 

     System.out.println("set size is "+set.size()); 
     System.out.println("set elements are "+set); 



    } 

} 


class Employee{ 

    private String name; 
    public String getName() { 
     return name; 
    } 
    public void setName(String name) { 
     this.name = name; 
    } 
    public int getNo() { 
     return no; 
    } 
    public void setNo(int no) { 
     this.no = no; 
    } 
    private int no; 
    @Override 
    public int hashCode() { 
     final int prime = 31; 
     int result = 1; 
     result = prime * result + ((name == null) ? 0 : name.hashCode()); 
     result = prime * result + no; 
     return result; 
    } 
    @Override 
    public boolean equals(Object obj) { 
     if (this == obj) 
      return true; 
     if (obj == null) 
      return false; 
     if (getClass() != obj.getClass()) 
      return false; 
     Employee other = (Employee) obj; 
     if (name == null) { 
      if (other.name != null) 
       return false; 
     } else if (!name.equals(other.name)) 
      return false; 
     if (no != other.no) 
      return false; 
     return true; 
    } 

}