java - 如何提高以下程序 "Remove duplicates from an array"的时间复杂度？

Question

我是数据结构和算法的新手。我正在研究一个问题集，它基本上是从数组中删除重复项并返回没有重复项的数组。我的目标是设计一个可以解决这个问题的高效算法。我使用编写 Naive 代码的方法，然后寻找各种方法来提高代码的时间复杂度。目前，我编写的代码的时间复杂度为 O(n^2)。所以，我想知道是否有人可以指出我的代码可能的改进，以便我可以将时间复杂度从 O(n^2) 降低到 O(nlogn) 或 O(n)(如果可能的话)。请我尝试在不对数组进行排序的情况下解决这个问题。谢谢。

public class MainClass {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
       int [] a= {1,7,7,7,9,9,10,10,10,11,11,1};
        removeduplicates(a);




    }

    public static void removeduplicates(int[]a)
    {
        int flag=0;
        int b =0;
        int k=0;
        int [] temp = new int[a.length];
        for(int i=0;i<a.length;i++)
        {
            int key = a[i];
            for(int j=i+1;j<a.length;j++)
            {
                if(key==a[j])
                {
                    flag++;

                }
            }

            if(flag==0)
            {
                temp[k] = key;
                k++;

            }

            else
            {
                for( int m=0;m<temp.length;m++)
                {
                    if(key==temp[m])
                    {
                        b++;
                    }
                }

                if(b==0)
                {
                    temp[k] = key;
                    k++;
                }
            }

            b = 0;
        }

        for(int i=0;i<k;i++)
            System.out.print(temp[i] +"\t");

    }


}

//下面的代码是对上面代码的改进，时间复杂度为O(n)。感谢@Bohemian 的建议:-

import java.util.HashSet;


public class MainClass {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
          HashSet<Integer> hs = new HashSet<Integer>();
           int [] a= {1,7,7,7,9,9,10,10,10,11,11,1};

           for(int i=0;i<a.length;i++)
           {
              hs.add(a[i]);
           }

           Integer [] rtrn = new Integer[hs.size()];
           rtrn = hs.toArray(rtrn);

           for(int i=0;i<rtrn.length;i++)
               System.out.print(rtrn[i] +"\t");

    }

}

Answer 1

伪代码中的 O(n) 解决方案是:

• 创建一个哈希集
• 对于每个值，如果集合中已经包含它，则丢弃它

因为 HashSet 上的所有操作都是 O(1)，而您执行了其中的 n 个操作，所以总体复杂度是 O(n)。

您可能会发现这一行很有用:

if (!set.add(i)) continue;

add()集合的方法返回 true如果集合被操作修改(即如果它还没有包含值)。