时间戳

首页 > 解决方案 > 从包含一对整数的列表中删除重复元素的复杂性

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

问题描述

我有一个包含成对整数示例的列表 -> [{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 个整数转换为单个字符串，然后将其插入哈希集中。有人可以告诉我上述代码的性能和时间复杂度吗？

标签： java

解决方案

快速复审：

set： set接口扩展集合接口。在一个集合中，不允许重复。集合中的每个元素都必须是唯一的。

hashset：使用哈希表实现。元素没有顺序。add、remove 和 contains 方法具有恒定的时间复杂度 O(1)。

要回答您的问题，请记住，我们将只关注任何操作中最昂贵的操作，这意味着如果我们的代码的某些部分具有 o(n) 和另一个 o(n^2) 的时间复杂度，那么我们将选择 o(n^2) 而不是 o(n) ，因为它是我们担心的最昂贵的。

首先，让我们谈谈空间复杂度，因为它很容易被发现，从您的代码中，您可以使用三个变量来存储更大的数据：

  1. 源代码
  2. 目的地
  3. 回答

第一个基本上具有 s(n) n 的空间复杂度，它是未经过滤的数据的原始大小（不是唯一的）。在上面 s(4) = 4 的示例中，注意：这意味着 4 * 您正在使用的数据类型大小，例如，如果您要存储整数列表，您会说 s(4(int)) = 4 *(4bytes) = 16bytes 的空间。

与上面相同的类比之后的第二个意味着我们有“src”的大小，“减去重复项” s(n) = 4 - 2(duplicates) = 2*(datatype size in bytes/bits)

第三个基本上只是成对存储来自“dest”的值，所以我们应该有基本相同的大小但数据类型不同。

这只是空间复杂度的基本转换，所以按照我们的规则，我们将保持最大的尺寸。所以，我们的空间复杂度是 s(n*(datatype size))，直接说 s(n) 是安全的。

对于时间复杂度，遵循相同的规则，我们需要在时间方面最昂贵的操作，这就是在“src”上执行的 for 循环，这是我们在这种情况下处理的任何数据的大小 4，所以我们可以说我们的时间复杂度是o(n)。

您的算法摘要：

空间复杂度：s(n)

时间复杂度：o(n)

性能相对平均。

推荐阅读