java - 从包含一对整数的列表中删除重复元素的复杂性

Question

我有一个包含整数对示例的列表 ->
[{1,2},{2,3},{2,1}]
我想从中删除重复元素，例如 (1,2) 和 (2,1) 相同。
这是我的代码->

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

在这里，我首先将 2 个整数转换为单个字符串，然后将其插入到 hashset 中。
有人可以告诉我上面代码的性能和时间复杂度吗？

Answer 1

自 HashSet用途 O(1) 为 contains方法，你的时间复杂度是 3N+c其中N是输入对的大小和 c是恒定的。所以总的时间复杂度是 O(N)。但是，您可以通过避免不必要的循环来改进代码。
你的空间复杂度也是3N+c这是 O(N) 的顺序。但是，您也可以改进这一点。
我建议扩展你的 pair 类以包含一个 equal 方法。

class Pair<t1,t2>
{
    int i, j;
    Pair(int i,int j){
        this.i=i;
        this.j=j;
    }

    public int getI() { return i;}
    public int getJ() { return j;}
    
   // Overriding equals() to compare two Complex objects
    @Override
    public boolean equals(Object o) {
  
        // If the object is compared with itself then return true  
        if (o == this) {
            return true;
        }

        Pair c = (Pair) o;
        if( (i==c.getI() && j==c.getJ() ) ||
            (i==c.getJ() && j==c.getI() ) ) {
             return true;
         }else {
            return false;
         }

}