Tìm kiếm, thêm, xoá phần tử trong mảng chưa được sắp xếp

Trong bài biết này, chúng ta sẽ cùng nhau thảo luận về tìm kiếm, thêm. xoá phần tử trong mảng chưa được sắp xếp.

Tìm kiếm

Một mảng chưa được sắp xếp, chúng ta có thể thực hiện bằng cách tìm duyệt hết tất cả các phần tử của mảng cho đến khi gặp được phần tử cần tìm.

Cho mảng arr[] = {1,7,5,6,2,9,8,-1}, tìm vị trí của phần tử có giá trị 5 trong mảng.

public class Main {

    public static void main(String[] args) {
        int[] arr = {1,7,5,6,2,9,8,-1};
        int x = 5;
        int pos = searchElement(arr, x);
        if (pos == -1){
            System.out.println("Khong tim thay");
        } else {
            System.out.println("Tim thay tai vi tri: " + pos);
        }
    }

    /**
     * @Param array[n] va X
     * return index[0, n - 1] neu tim thay
     * return -1 neu khong tim thay
     */
    static int searchElement(int[] arr, int x) {
        for(int i = 0; i < arr.length; i++) {
            if (arr[i] == x)
                return i;
        }
        return -1;
    }
}

Output: Tim thay tai vi tri: 2

Thêm

Một mảng chưa được sắp xếp, khi thêm chúng ta chỉ cần thêm cuối mảng nếu không có yêu cầu gì thêm.

public class Main {

    public static void main(String[] args) {
        int size = 20; // Suc chua cua mang
        int[] arr = new int[size];
        arr[0] = 1;
        arr[1] = -1;
        arr[2] = 6;
        arr[3] = 5;
        arr[4] = 3;
        int n = 5; // So luong phan tu trong mang hien tai
        int x = 10;

        System.out.print("Truoc khi them: ");
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");

        // Inserting key
        n = insert(arr, size, n, x);

        System.out.print("\nSau khi them: ");
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");

    }

    static int insert(int[] arr, int size, int n, int x) {
        // Neu so luong phan tu lon hon hoac bang suc chua cua mang thi khong the them
        if (n >= size) {
            return n;
        }
        // them X vao vi tri cuoi cua mang
        arr[5] = x;
        return n + 1; // tang so luong phan tu cua mang them 1
    }
}

Output:
Before Insertion: 1 -1 6 5 3
After Insertion: 1 -1 6 5 3 10

Vậy nếu chúng ta cần thêm phần tử x vào vị trí postion trong mảng thì phải làm sao?

Nhìn vào ảnh trên, ta cần dịch chuyển 1 đơn vị cho tất cả các phần tử từ vị trí postion trở về sau, sau đó chèn phần tử cần thêm vào vị trí postion.

static int insertToPos(int[] arr, int size, int n, int x, int postision) {
        // Neu so luong phan tu lon hon hoac bang suc chua cua mang thi khong the them
        if (n >= size) {
            return n;
        }
        // vi tri them phan tu phai thuoc khoang[0, n]
        if (postision < 0 || postision > n) {
            return n;
        }

        for(int i = n; i > postision; i--) {
            arr[i] = arr[i - 1];
        }
        // them X vao vi tri postision cua mang
        arr[postision] = x;
        return n + 1; // tang so luong phan tu cua mang them 1
    }

Xoá

Để xoá một phần tử trong mảng, đầu tiên chúng ta cần tìm vị trí của phần tử cần xoá nằm trong mảng(pos), sau đó tiến hàng dịch chuyển các phần tử từ vị trí pos + 1 sang trái.

 

public class Main {

    public static void main(String[] args) {
        int size = 20; // Suc chua cua mang
        int[] arr = new int[size];
        arr[0] = 1;
        arr[1] = -1;
        arr[2] = 6;
        arr[3] = 5;
        arr[4] = 3;
        int n = 5; // So luong phan tu trong mang hien tai

        System.out.print("Truoc khi xoa: ");
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");

        int x = 6;
        n = delete(arr, n, x);

        System.out.print("\nSau khi xoa : ");
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");

    }

    static int delete(int[] arr, int n, int key) {
        int pos = searchElement(arr, key);
        if (pos == -1) {
            System.out.println("Khong tim thay phan tu can xoa");
        }

        // Xoa phan tu
        for (int i = pos; i < n; i++) {
            arr[i] = arr[i + 1];
        }
        return n - 1;

    }

    static int searchElement(int[] arr, int x) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == x)
                return i;
        }
        return -1;
    }
}

Output:
Truoc khi xoa: 1 -1 6 5 3
Sau khi xoa : 1 -1 5 3