如何在Java中从ArrayList中删除重复的对

Question

我有一个ArrayList，它包含成对的整数(比如int I，int j(。但它可能包含重复的对(如(int i, int j)和(int j, int i)(。现在，我如何在O(n(时间复杂性中从中删除重复项。

更新代码：

class Pair<t1,t2>
{
int i, j;
Pair(int i,int j){
this.i=i;
this.j=j;
}
}
public class My 
{
public static void main(String[] args) {
Pair p;
List<Pair<Integer,Integer>> src = Arrays.asList(new Pair(1,2), 
new Pair(2,3), new Pair(2,1),new Pair(1,2));
HashSet<String> dest  = new HashSet();
for(int i=0; i < src.size(); i++) {
p=src.get(i);
if(dest.contains(p.j+" "+p.i)) {
System.out.println("duplicacy");
}  
else {
dest.add(p.i+" "+p.j);
}

}
System.out.println("set is = "+dest);

List<Pair<Integer,Integer>> ans=new ArrayList();
String temp;
int i,j;
Iterator<String> it=dest.iterator();
while(it.hasNext()) 
{
temp=it.next();
i=Integer.parseInt(temp.substring(0,temp.indexOf(' ')));
j=Integer.parseInt(temp.substring(temp.indexOf(' 
')+1,temp.length()));
ans.add(new Pair(i,j));
}

for(Pair i_p:ans) {
System.out.println("Pair = "+i_p.i+" , "+i_p.j);
}
}//end of main method
}//end of class My

这段代码运行良好，但我想知道它的性能，我指的是它的总体时间复杂性？

Answer 1

• 如果可以修改Pair类，只需实现equals()和hashCode()：

  public class Pair {
  private int a;
  private int b;
  public Pair(int a, int b) {
  this.a = a;
  this.b = b;
  }
  @Override
  public boolean equals(Object o) { 
  if (this == o) return true;
  if (o == null || getClass() != o.getClass()) return false;
  Pair pair = (Pair) o;
  return (a == pair.a && b == pair.b) || (a == pair.b && b == pair.a);
  }
  @Override
  public int hashCode() {
  return Objects.hashCode(new HashSet<>(Arrays.asList(a,b))); 
  }
  @Override
  public String toString() {
  return "Pair{" +
  "a=" + a +
  ", b=" + b +
  '}';
  }
  }
  

  然后创建一个新的Set<Pair>:

  List<Pair> pairs = Arrays.asList(new Pair(1, 2), new Pair(2, 1), new Pair(3, 2));
  Set<Pair> pairSet = new HashSet<>(pairs);
  System.out.println(pairSet);
  

  输出：

  [Pair{a=1, b=2}, Pair{a=3, b=2}]
  

• 如果不能修改Pair类：

  List<Pair> pairs = Arrays.asList(new Pair(1, 2), new Pair(2, 1), new Pair(3, 2));
  Set<Pair> pairSet = pairs.stream()
  .map(pair -> new HashSet<>(Arrays.asList(pair.getA(), pair.getB())))
  .distinct()
  .map(integers -> {
  Iterator<Integer> iterator = integers.stream().iterator();
  return new Pair(iterator.next(), iterator.next());
  })
  .collect(Collectors.toSet());
  System.out.println(pairSet);
  

  输出：

  [Pair{a=1, b=2}, Pair{a=2, b=3}]
  

---

如果您愿意，您可以将Set转换回列表：

List<Pair> list = new ArrayList<>(set);

但这很可能是不必要的。

Answer 2

只在Pairs列表中进行一次循环，并通过HashSet处理的pair中的方式进行收集，然后进行反向复制：

List<Pair<Integer,Integer>> lp = Arrays.asList(new Pair(1,2),
new Pair(2,3),
new Pair(1,2),
new Pair(2,1));
Set<Pair<Integer,Integer>> sp = new HashSet<>();
List<Pair<Integer,Integer>> ulp = lp.stream()
.collect(ArrayList::new,
(l,p)-> { Pair<Integer,Integer> p1 = new Pair(p.getValue(), p.getKey());
if (!(sp.contains(p))&&!(sp.contains(p1))){
l.add(p);
sp.add(p);
sp.add(p1);
}} , List::addAll);
System.out.println(ulp);

Answer 3

由于HashSet的contains((在O(1(时间内运行(请参阅本文和其他参考文献(，您可以使用以下方法，即总体O(n(：

import java.util.*;
import javafx.util.*;
public class Main
{
public static void main(String[] args) {
List<Pair<Integer,Integer>> src = Arrays.asList(new Pair(1,2), new Pair(2,3), new Pair(2,1));
HashSet<Pair<Integer,Integer>> dest  = new HashSet();
for(int i=0; i < src.size(); i++) {
if(dest.contains(src.get(i)) || 
dest.contains(new Pair(src.get(i).getValue(),src.get(i).getKey()))) {

}else {
dest.add(src.get(i));
}
}

System.out.println(dest);
}
}

编辑1：

您可以使用Map.Entry而不是javafx.util.pair。在没有Javafx的情况下执行程序如下。

import java.util.*;
public class Main
{
public static void main(String[] args) {
List<Map.Entry<Integer,Integer>> src = Arrays.asList(new AbstractMap.SimpleEntry(1,2), 
new AbstractMap.SimpleEntry(2,3), new AbstractMap.SimpleEntry(2,1));
HashSet<Map.Entry<Integer,Integer>> dest  = new HashSet();
for(int i=0; i < src.size(); i++) {
if(dest.contains(src.get(i)) || 
dest.contains(new AbstractMap.SimpleEntry(src.get(i).getValue(),src.get(i).getKey()))) {

}else {
dest.add(src.get(i));
}
}

System.out.println(dest);
}
}