Làm cách nào để loại bỏ các phần tử trùng lặp trong quá trình sắp xếp mảng theo thứ tự tăng dần sử dụng Bubble Sort?

[1303Linh (Linh Đặng)]

Chào mọi người ạ, mọi người cho em hỏi có cách nào để loại bỏ các phần tử trùng lặp trong quá trình sắp xếp một mảng số nguyên theo thứ tự tăng dần không ạ? Em sử dụng Bubble Sort, và dưới đây là code phần removeDuplicates() em đã viết ạ:

/*
 Sắp xếp một array intergers + loại bỏ các phần tử trùng lặp khỏi mảng
 {5, 2, 7, 2, 8, 5, 3}
 */

    static void removeDuplicates(int[] arr){

        int n = arr.length;
        int [] newArr = new int[n]; // Tạo một mảng mới có cùng kích thước với arr
        newArr[0] = arr[0]; // Sao chép phần tử đầu tiên từ arr sang newArr
        int newSize = 1;
/*
   * Kiếm tra xem arr[i] có giống với một trong những phần tử đã được sao chép vào newArr[] hay không
         */
        for(int i = 1; i < n; ++i){
            boolean isDuplicate = false;
            for (int j = 0; j < newSize; j++){
                if(arr[i] == newArr[j]){
                    isDuplicate = true;
                    break;
                }
             }
        }
        if(!isDuplicate){
            newArr[newSize] = arr[i];
            newSize++;
        }
 /*
     * Tạo một mảng mới 'trimmedArr' có kích thước 'newSize' => Sao chép các phần tử từ mảng 'newArr' vào mảng mới này
         * Vòng lặp for duyệt qua các phần tử của 'newArr' tới chỉ mục 'newSize - 1' => Sao chép vào 'trimmedArr' ở vị trí tương ứng
         */
        int[] trimmedArr = new int[newSize];
        for (int i = 0; i < newSize; ++i){
            trimmedArr[i] = newArr[i];
        }  
        for (int a = 0; a< newSize; ++a){
            arr[a] = trimmedArr[a];
        }
   } 

Sau đó em tạo phương thức bubbleSort() để sắp xếp mảng và cuối cùng là trình chiếu mảng bằng printArray().

Đây là cách mà em đã thử sử dụng nhưng vẫn không loại bỏ được các phần tử trùng lặp ạ:

1. HashSet

   HashSet<Integer> set = new HashSet<>();
       int newSize = 0; 
   
       for(int num: arr){
           if(!set.contains(num)){
               set.add(num);
               arr[newSize++] = num;
           }
       }
   

Mọi người cho em xin ý kiến ạ! Em cảm ơn ạ!

[kisuluoibieng (Tên Gì Cũng Được)]

vòng for j của bạn, đang chạy từ đâu đến đâu?
và khi for j kết thúc, bạn làm gì?
mỗi vòng for i của bạn để làm gì

[1303Linh (Linh Đặng)]

1. Vòng for ‘j’ của em đang chạy từ đầu tới cuối mảng newArr[ ] có length = newSize.

2. Khi vòng for ‘j’ kết thúc, em sẽ có thể copy được các phần tử từ arr[] vào newArr[]
   -> và trong quá trình so sánh, em check được nếu trong các phần tử được copy vào có phần tử nào trùng lặp với phần tử đã có trong newArr[] thì break tại đó và xét tiếp các phần tử tiếp theo.

• Có chỗ này em bị copy code vào nhầm ạ:

     for(int i = 1; i < n; ++i){
            boolean isDuplicate = false;
            for (int j = 0; j < newSize; j++){
                if(arr[i] == newArr[j]){
                    isDuplicate = true;
                    break;
                }
             }
             if(!isDuplicate){
            newArr[newSize] = arr[i];
            newSize++;
            }

• Vòng for ‘i’ đầu tiên để duyệt các phần tử trong arr[], cứ mỗi phần tử trong arr[] được xét tới để copy vào newArr[] -> vòng lặp sẽ duyệt qua một lượt tất cả các phần tử trong newArr[] để so sánh và xác định không có phần tử nào trùng lặp.

• Vòng for ‘i’ thứ 2 là để copy tất cả các phần tử trong newArr[] vào một mảng trung gian là trimmedArr[], sau đó lại gán tất cả các phần tử từ mảng trung gian này vào mảng arr[] ban đầu.

Đây là phần lý giải của em ạ, em cảm ơn ạ!

[kisuluoibieng (Tên Gì Cũng Được)]

@1303Linh

Sau đó em tạo phương thức bubbleSort() để sắp xếp mảng và cuối cùng là trình chiếu mảng bằng printArray().

sắp xếp mảng nào?
code sắp xếp ở đâu?

@1303Linh

HashSet set = new HashSet<>(); int newSize = 0; for(int num: arr){ if(!set.contains(num)){ set.add(num); arr[newSize++] = num; } }

đoạn này có liên quan gì với đoạn trên không?
full code như nào?

[1303Linh (Linh Đặng)]

1. Sắp xếp lại mảng arr[] đã được loại bỏ các phần tử trùng lặp ạ.
2. Code sắp xếp:

static void bubbleSort(int[] arr){
        int n = arr.length;
        for(int i = 0; i < n-1; ++i){
            for(int j = 0; j< n-i-1; ++j){
                if(arr[j] > arr[j+1]){
                    int maxtemp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = maxtemp;
                }
            }
        }
    }

3. Đoạn này tức là thay vì phải dùng nhiều các vòng for như trên thì em sẽ thay bằng cách dùng HashSet ạ.
4. Full code:

// Thiết lập hàm removeDuplicates()
static void removeDuplicates(int[] arr) {
        HashSet<Integer> set = new HashSet<>();
        int index = 0;
        
        for (int num : arr) {
            if (!set.contains(num)) {
                set.add(num);
                arr[index++] = num;
            }
        }

        int[] trimmedArr = new int[index];
        for (int i = 0; i < index; i++) {
            trimmedArr[i] = arr[i];
        }

        // Gán lại các phần tử duy nhất vào mảng ban đầu
        for (int i = 0; i < index; i++) {
            arr[i] = trimmedArr[i];
        }
    }

Em cảm ơn ạ!

[bienjouer]

Hàm removeDuplicates của bạn sao đã dùng set, rồi còn thêm trimmedArray, rồi copy arr sang trimmedArray, rồi copy ngc lại thế, mình không hiểu lắm

Bạn thử như này xem

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.stream.Collectors;

public class Main {

    public static void main(String[] args) {

        int[] arr = {1, 2, 2, 3, 4, 4, 5, 6, 6, 7};


        arr = removeDuplicates(arr);


        System.out.println("Array after removing duplicates: " + Arrays.toString(arr));
    }

    static int[] removeDuplicates(int[] arr) {
        Set<Integer> set = new HashSet<>();
        for (int num : arr) {
            set.add(num);
        }


        return set.stream().mapToInt(Integer::intValue).toArray();
    }
}