Program Java untuk mengalih keluar pendua daripada timbunan tertentu-javaTutorial-php.cn

Dalam artikel ini, kami akan meneroka dua kaedah untuk mengalih keluar elemen pendua daripada timbunan di Java. Kami akan membandingkan pendekatan mudah dengan gelung bersarang dan kaedah yang lebih cekap menggunakan HashSet. Matlamatnya ialah untuk menunjukkan cara mengoptimumkan penyingkiran pendua dan menilai prestasi setiap pendekatan.

Pernyataan masalah

Tulis atur cara Java untuk mengalih keluar elemen pendua daripada timbunan.

Input

Stack<Integer> data = initData(10L);

Salin selepas log masuk

Output

Unique elements using Naive Approach: [1, 4, 3, 2, 8, 7, 5]
Time spent for Naive Approach: 18200 nanoseconds

Unique elements using Optimized Approach: [1, 4, 3, 2, 8, 7, 5]
Time spent for Optimized Approach: 34800 nanoseconds

Salin selepas log masuk

Untuk mengalih keluar pendua daripada timbunan tertentu, kami mempunyai 2 pendekatan −

Pendekatan naif: Cipta dua gelung bersarang untuk melihat elemen yang sudah ada dan menghalangnya daripada menambahkannya pada pulangan timbunan hasil.
Pendekatan HashSet: Gunakan Set untuk menyimpan elemen unik, dan manfaatkan kerumitan O(1)nya untuk menyemak sama ada elemen ada atau tidak.

Menjana dan mengklon tindanan rawak

Di bawah ialah program Java mula-mula membina tindanan rawak dan kemudian mencipta pendua untuk kegunaan selanjutnya −

private static Stack initData(Long size) {
    Stack stack = new Stack < > ();
    Random random = new Random();
    int bound = (int) Math.ceil(size * 0.75);
    for (int i = 0; i < size; ++i) {
        stack.add(random.nextInt(bound) + 1);
    }
    return stack;
}

private static Stack < Integer > manualCloneStack(Stack < Integer > stack) {
    Stack < Integer > newStack = new Stack < > ();
    for (Integer item: stack) {
        newStack.push(item);
    }
    return newStack;
}

Salin selepas log masuk

initData membantu mencipta Tindanan dengan saiz yang ditentukan dan unsur rawak antara 1 hingga 100.

manualCloneStack membantu menjana data dengan menyalin data daripada tindanan lain, menggunakannya untuk perbandingan prestasi antara kedua-dua idea.

Alih keluar pendua daripada timbunan tertentu menggunakan pendekatan Naïve

Berikut ialah langkah untuk mengalih keluar pendua daripada timbunan tertentu menggunakan pendekatan Naïve −

Mulakan pemasa.
Buat tindanan kosong untuk menyimpan elemen unik.
Lelaran menggunakan gelung while dan teruskan sehingga tindanan asal kosong, pop elemen atas.
Semak pendua menggunakan resultStack.contains(element) untuk melihat sama ada elemen itu sudah ada dalam tindanan hasil.
Jika elemen tiada dalam tindanan hasil, tambahkannya pada resultStack.
Rekod masa tamat dan hitung jumlah masa yang dihabiskan.
Pulangan hasil

Contoh

Di bawah ialah program Java untuk mengalih keluar pendua daripada timbunan tertentu menggunakan pendekatan Naïve −

public static Stack idea1(Stack stack) {
  long start = System.nanoTime();
  Stack resultStack = new Stack < > ();

  while (!stack.isEmpty()) {
    int element = stack.pop();
    if (!resultStack.contains(element)) {
      resultStack.add(element);
    }
  }
  System.out.println("Time spent for idea1 is %d nanosecond".formatted(System.nanoTime() - start));
  return resultStack;
}

Salin selepas log masuk

Untuk pendekatan Naif, kami menggunakan

<code>while (!stack.isEmpty())</code>

Salin selepas log masuk

untuk mengendalikan gelung pertama untuk melalui semua elemen dalam tindanan, dan gelung kedua ialah


    <div class="code" style="position:relative; padding:0px; margin:0px;"><pre class="brush:php;toolbar:false">resultStack.contains(element)</pre><div class="contentsignin">Salin selepas log masuk</div></div>

untuk menyemak sama ada elemen itu sudah ada.

Alih keluar pendua daripada tindanan tertentu menggunakan pendekatan yang dioptimumkan (HashSet)

Berikut ialah langkah untuk mengalih keluar pendua daripada timbunan tertentu menggunakan pendekatan yang dioptimumkan −

Mulakan pemasa
Buat Set untuk menjejak elemen yang dilihat (untuk semakan kerumitan O(1).
Buat timbunan sementara untuk menyimpan elemen unik.
Lelaran menggunakan gelung sambil teruskan sehingga tindanan kosong .
Alih keluar elemen atas daripada timbunan.
Untuk menyemak pendua kami akan menggunakan dilihat.mengandungi(elemen) untuk menyemak sama ada elemen itu sudah ada dalam set.
Jika elemen tiada dalam set, tambahkannya pada timbunan yang dilihat dan sementara.
Rekod masa tamat dan hitung jumlah masa yang dihabiskan.
Kembalikan hasilnya

Contoh

Di bawah ialah program Java untuk mengalih keluar pendua daripada timbunan tertentu menggunakan HashSet −

public static Stack<Integer> idea2(Stack<Integer> stack) {
    long start = System.nanoTime();
    Set<Integer> seen = new HashSet<>();
    Stack<Integer> tempStack = new Stack<>();

    while (!stack.isEmpty()) {
        int element = stack.pop();
        if (!seen.contains(element)) {
            seen.add(element);
            tempStack.push(element);
        }
    }
    System.out.println("Time spent for idea2 is %d nanosecond".formatted(System.nanoTime() - start));
    return tempStack;
}

Salin selepas log masuk

Untuk pendekatan yang dioptimumkan, kami menggunakan

<code>Set<Integer> seen</code>

Salin selepas log masuk

to menyimpan elemen unik dalam Set, manfaatkan O(1) kerumitan apabila mengakses elemen rawak untuk mengurangkan kos pengiraan untuk menyemak sama ada elemen ada atau tidak.

Menggunakan kedua-dua pendekatan bersama

Di bawah ialah langkah untuk mengalih keluar pendua daripada timbunan tertentu menggunakan kedua-dua pendekatan yang disebutkan di atas -

Memulakan data yang kami gunakan kaedah initData(Saiz panjang) untuk mencipta tindanan yang diisi dengan integer rawak.
Klon Tindanan yang kita gunakan kaedah cloneStack(Timbunan) untuk mencipta salinan tepat tindanan asal.
initData.
cloneStack.
pendekatan naif untuk mengalih keluar pendua daripada timbunan asal.
pendekatan dioptimumkan untuk mengalih keluar pendua daripada timbunan klon.

Contoh

Di bawah ialah program Java yang mengalih keluar elemen pendua daripada timbunan menggunakan kedua-dua pendekatan yang dinyatakan di atas −

import java.util.HashSet;
import java.util.Random;
import java.util.Set;
import java.util.Stack;

public class DuplicateStackElements {
    private static Stack<Integer> initData(Long size) {
        Stack<Integer> stack = new Stack<>();
        Random random = new Random();
        int bound = (int) Math.ceil(size * 0.75);
        for (int i = 0; i < size; ++i) {
            stack.add(random.nextInt(bound) + 1);
        }
        return stack;
    }
    private static Stack<Integer> cloneStack(Stack<Integer> stack) {
        Stack<Integer> newStack = new Stack<>();
        newStack.addAll(stack);
        return newStack;
    }
    public static Stack<Integer> idea1(Stack<Integer> stack) {
        long start = System.nanoTime();
        Stack<Integer> resultStack = new Stack<>();

        while (!stack.isEmpty()) {
            int element = stack.pop();
            if (!resultStack.contains(element)) {
                resultStack.add(element);
            }
        }
        System.out.printf("Time spent for idea1 is %d nanoseconds%n", System.nanoTime() - start);
        return resultStack;
    }
    public static Stack<Integer> idea2(Stack<Integer> stack) {
        long start = System.nanoTime();
        Set<Integer> seen = new HashSet<>();
        Stack<Integer> tempStack = new Stack<>();

        while (!stack.isEmpty()) {
            int element = stack.pop();
            if (!seen.contains(element)) {
                seen.add(element);
                tempStack.push(element);
            }
        }
        System.out.printf("Time spent for idea2 is %d nanoseconds%n", System.nanoTime() - start);
        return tempStack;
    }
    public static void main(String[] args) {
        Stack<Integer> data1 = initData(10L);
        Stack<Integer> data2 = cloneStack(data1);
        System.out.println("Unique elements using idea1: " + idea1(data1));
        System.out.println("Unique elements using idea2: " + idea2(data2));
    }
}

Salin selepas log masuk

Output

Java program to remove duplicates from a given stack

Perbandingan

* Unit ukuran ialah nanosaat.

public static void main(String[] args) {
    Stack<Integer> data1 = initData(<number of stack size want to test>);
    Stack<Integer> data2 = manualCloneStack(data1);
    idea1(data1);
    idea2(data2);
}

Salin selepas log masuk

Method	100 elements	1000 elements	10000 elements	100000 elements	1000000 elements
Idea 1	693100	4051600	19026900	114201800	1157256000
Idea 2	135800	681400	2717800	11489400	36456100

As observed, the time running for Idea 2 is shorter than for Idea 1 because the complexity of Idea 1 is O(n²), while the complexity of Idea 2 is O(n). So, when the number of stacks increases, the time spent on calculations also increases based on it.

Atas ialah kandungan terperinci Program Java untuk mengalih keluar pendua daripada timbunan tertentu. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!