Как я могу улучшить временную сложность следующей программы «Удалить дубликаты из массива»?

java arrays algorithm data-structures

69 просмотра

1 ответ

Я новичок в структурах данных и алгоритмах. Я работал над набором задач, который в основном заключается в удалении дубликатов из массива и возвращении массива без дубликатов. Моей целью было разработать эффективный алгоритм, который может решить эту проблему. Я использовал подход написания наивного кода, а затем нашел различные способы улучшить временную сложность кода. В настоящее время код, который я написал, имеет временную сложность 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");

    }

}
Автор: Melissa Источник Размещён: 08.11.2019 11:17

Ответы (1)


3 плюса

Решение

O (n) решение в псевдокоде:

  • создать HashSet
  • для каждого значения отбросьте его, если оно уже содержится в наборе

Поскольку все операции в HashSet являются O (1), а вы выполняете n из них, общая сложность составляет O (n).

Вы можете найти эту строку полезной:

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

add()Метод из набора возвращается , trueесли набор был изменен с помощью операции (то есть , если он уже не содержит значения).

Автор: Bohemian Размещён: 20.08.2016 12:29
Вопросы из категории :
32x32