1.7K 90 69

Đã đăng vào May 21st, 2023 9:03 a.m. 14 phút đọc

Chương 11: SEARCHING - Problems & Solutions(19-37)

Problem-19

Tìm hai phần tử lặp lại trong một mảng đã cho: Cho một mảng có kích thước, tất cả các phần tử của mảng nằm trong phạm vi từ 1 đến n và tất cả các phần tử chỉ xuất hiện một lần trừ hai số xuất hiện hai lần. Tìm hai số lặp lại đó. Ví dụ: nếu mảng là 4,2,4,5,2,3,1 với kích thước = 7 và n = 5. Đầu vào này có n + 2 = 7 phần tử với tất cả các phần tử xuất hiện một lần ngoại trừ 2 và 4 xuất hiện hai lần. Vì vậy, output phải là 4 2.

Solution: Một cách đơn giản là quét toàn bộ mảng để tìm từng phần tử của các phần tử đầu vào. Điều đó có nghĩa là sử dụng hai vòng lặp. Trong vòng lặp bên ngoài, chọn từng phần tử một và đếm số lần xuất hiện của phần tử được chọn trong vòng lặp bên trong.

    public void PrintRepeatedElements(int[] A){
        for (int i = 0; i < A.length; i++) {
            for (int j = i+1; j < A.length; j++) {
                if(A[i] == A[j]){
                    System.out.println(A[i]);
                }
            }
        }
    }

Time Complexity: $O(n^2)$ . Space Complexity: $O(1)$ .

Problem-20

Đối với Problem-19, chúng ta có thể cải thiện độ phức tạp của thời gian không?

Solution: Sắp xếp mảng bằng bất kỳ thuật toán sắp xếp so sánh nào và xem liệu có bất kỳ phần tử nào liền kề với cùng một giá trị hay không.

Time Complexity: $O(nlogn)$ . Space Complexity: O(1).

Problem-21

Đối với Problem-19, chúng ta có thể cải thiện độ phức tạp của thời gian không?

Solution: Sử dụng Count Array(Mảng đếm). Giải pháp này giống như sử dụng bảng băm. Để đơn giản, chúng ta có thể sử dụng mảng để lưu trữ số đếm. Duyệt qua mảng một lần và theo dõi số lượng của tất cả các phần tử trong mảng bằng cách sử dụng số lượng mảng tạm thời có kích thước n. Khi chúng tôi thấy một phần tử có số lượng đã được đặt, hãy in nó dưới dạng trùng lặp.

    public void PrintRepeatedElements(int[] A){
        int count[] = new int[A.length - 2];
        for (int i = 0; i < A.length; i++) {
            count[A[i]]++;
            if (count[A[i]] == 2){
                System.out.println(A[i]);
            }
        }
    }

Time Complexity: O(n). Space Complexity: O(n).

Problem-22

Đối với Problem-19, chúng ta có thể cải thiện độ phức tạp không?

Solution: Có, bằng cách sử dụng XOR Operation. Cho các số lặp là X và Y, nếu ta XOR tất cả các phần tử trong mảng và cả các số nguyên từ 1 đến n thì kết quả sẽ là $X$ $XOR$ $Y$ . Số 1 trong biểu diễn nhị phân của $X$ $XOR$ $Y$ tương ứng với các bit khác nhau giữa X và Y.

Nếu bit thứ k của $X$ $XOR$ $Y$ là 1, chúng ta có thể $XOR$ tất cả các phần tử trong mảng và tất cả các số nguyên từ 1 đến n có bit thứ k là 1. Kết quả sẽ là một trong X và Y.

class RepeatElement {
    void printRepeating(int arr[], int size)
    {
        /* Will hold xor of all elements */
        int xor = arr[0];
 
        /* Will have only single set bit of xor */
        int set_bit_no;
 
        int i;
        int n = size - 2;
        int x = 0, y = 0;
 
        /* Get the xor of all elements in arr[] and {1, 2 ..
         * n} */
        for (i = 1; i < size; i++)
            xor ^= arr[i];
        for (i = 1; i <= n; i++)
            xor ^= i;
 
        /* Get the rightmost set bit in set_bit_no */
        set_bit_no = (xor & ~(xor - 1));
 
        /* Now divide elements in two sets by comparing
           rightmost set bit of xor with bit at same
           position in each element. */
        for (i = 0; i < size; i++) {
            int a = arr[i] & set_bit_no;
            if (a != 0)
                x = x
                    ^ arr[i]; /*XOR of first set in arr[] */
            else
                y = y ^ arr[i]; /*XOR of second set in arr[]
                                 */
        }
        for (i = 1; i <= n; i++) {
            int a = i & set_bit_no;
            if (a != 0)
                x = x ^ i; /*XOR of first set in arr[] and
                              {1, 2, ...n }*/
            else
                y = y ^ i; /*XOR of second set in arr[] and
                              {1, 2, ...n } */
        }
 
        System.out.print("Repeating elements are ");
        System.out.println(y + " " + x);
    }
 
    /* Driver program to test the above function */
    public static void main(String[] args)
    {
        RepeatElement repeat = new RepeatElement();
        int arr[] = { 4, 2, 4, 5, 2, 3, 1 };
        int arr_size = arr.length;
        repeat.printRepeating(arr, arr_size);
    }
}

Time Complexity: O(n). Space Complexity: O(1).

Problem-23

Đối với Problem-19, chúng ta có thể cải thiện độ phức tạp không?

Solution: Chúng ta có thể giải quyết vấn đề này bằng cách lập hai phương trình toán học đơn giản. Giả sử rằng hai số chúng ta sẽ tìm là X và Y. Ta biết tổng của n số là $n(n + 1)/2$ và tích là $n!$ . Lập hai phương trình bằng cách sử dụng các công thức tính tổng và tích này, đồng thời nhận giá trị của hai ẩn số bằng cách sử dụng hai phương trình. Đặt tổng của tất cả các số trong mảng là S và tích là P và các số đang được lặp lại là X và Y.

Sử dụng hai phương trình trên, chúng ta có thể tìm ra X và Y. Có thể có một vấn đề tràn số cộng và nhân nếu số quá lớn với cách tiếp cận này.

Time Complexity: O(n). Space Complexity: O(1).

Problem-24

Tương tự như Problem-19, giả sử rằng các số nằm trong phạm vi từ 1 đến n. Ngoài ra, n – 1 các phần tử được lặp lại ba lần và phần tử còn lại được lặp lại hai lần.

Solution: Nếu chúng ta XOR tất cả các phần tử trong mảng và tất cả các số nguyên từ 1 đến n, thì tất cả các phần tử được lặp lại ba lần sẽ trở thành số không. Điều này là do, vì phần tử đang lặp lại ba lần và XOR một lần khác làm cho phần tử đó xuất hiện bốn lần. Kết quả là, đầu ra của a XOR a XOR a XOR a = 0. Đó là trường hợp tương tự với tất cả các phần tử được lặp lại ba lần. Với logic tương tự, đối với phần tử lặp lại hai lần, nếu chúng ta XOR các phần tử đầu vào và cả phạm vi, thì tổng số lần xuất hiện của phần tử đó là 3. Kết quả là, đầu ra của a XOR a XOR a = a. Cuối cùng, chúng ta nhận được phần tử lặp lại hai lần.

Time Complexity: O(n). Space Complexity: O(1).

Problem-25

Cho một mảng các số nguyên, mỗi phần tử xuất hiện hai lần trừ một phần tử. Tìm phần tử duy nhất đó.

Solution: Thực hiện phép dịch bit XOR tất cả các phần tử. Chúng ta sẽ nhận được kết quả phần tử xuất hiện 1 lần.

    public int singleMissingNumber(int[] A){
        int missingNum = A[0];
        for (int i = 0; i < A.length; i++) {
            missingNum ^= A[i];
        }
        return missingNum;
    }

Time Complexity: O(n). Space Complexity: O(1).

Problem-27

Cho một mảng gồm n phần tử. Tìm hai phần tử trong mảng sao cho tổng của chúng bằng K?

Solution: Một giải pháp đơn giản cho vấn đề này là đối với mỗi phần tử đầu vào, hãy kiểm tra xem có phần tử nào có tổng bằng K hay không. Điều này chúng ta có thể giải quyết chỉ bằng cách sử dụng hai vòng lặp for đơn giản. Mã cho giải pháp này có thể được đưa ra là:

public void twoSumK(int[] A, int K){
        for (int i = 0; i < A.length; i++) {
            for (int j = i; j < A.length; j++) {
                if (A[i] + A[j] == K){
                    System.out.println("Items Found, i: " + i + " j:" + j);
                    return;
                }
                
            }
        }
        System.out.println("Items not found: No such elements");
    }

Time Complexity: $O(n^2)$ . Space Complexity: $O(1)$ .

Problem-28

Đối với Problem-27, chúng ta có thể cải thiện độ phức tạp của thời gian không?

Solution: Yes. Giả sử rằng chúng ta đã sắp xếp mảng đã cho. Thao tác này mất O(n logn). Trên mảng đã sắp xếp, duy trì các chỉ số loIndex = 0 và hiIndex = n – 1 rồi tính A[loIndex] + A[hiIndex]. Nếu tổng bằng K, thì chúng ta đã hoàn thành giải pháp. Nếu tổng nhỏ hơn K thì giảm hiIndex, nếu tổng lớn hơn K thì tăng loIndex.

    public void twoSumK(int[] A, int K){
        int i, j, temp;
        Arrays.sort(A);
        for (i = 0, j = A.length-1; i<j;) {
            temp = A[i] + A[j];
            if (temp == K){
                System.out.println("Items found, i: " + i + " j:" + j);
                return;
            } else if (temp < K) {
                i++;
            } else {
                j--;
            }
        }
    }

Time Complexity: O(nlogn). Nếu mảng đã cho đã được sắp xếp thì độ phức tạp là O(n). Space Complexity: O(1).

Problem-29

Solution của Problem-27 có hoạt động ngay cả khi mảng không được sắp xếp không?

Solution: Vì chúng ta đang kiểm tra tất cả các khả năng nên thuật toán đảm bảo rằng chúng tôi nhận được cặp số nếu chúng tồn tại.

Problem-30

Có cách nào khác để giải Problem-27 không?

Solution: Yes, sử dụng hash table. Vì mục tiêu của chúng ta là tìm hai chỉ số của mảng có tổng là K. Giả sử các chỉ số đó là X và Y. Điều đó có nghĩa là, A[X] + A[Y] = K. Điều chúng ta cần là, đối với mỗi phần tử của mảng đầu vào A[X], hãy kiểm tra xem K – A[X] có tồn tại trong mảng đầu vào hay không. Bây giờ, chúng ta hãy đơn giản hóa việc tìm kiếm đó bằng bảng băm.

Algorithm:

Đối với mỗi phần tử của mảng đầu vào, hãy chèn vào hash table. Giả sử phần tử hiện tại là A[X].
Trước khi chuyển sang phần tử tiếp theo, chúng ta kiểm tra xem K - A[X] có tồn tại trong bảng băm hay không.
Sự tồn tại của số như vậy cho thấy rằng chúng tôi có thể tìm thấy các index.
Nếu không thì chuyển sang phần tử đầu vào tiếp theo.

public void twoSumK(int[] A, int K){
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < A.length; i++) {
            if (map.containsKey(K - A[i])){
                System.out.println("Items Found, i: " + i + " j:" + map.get(K - A[i]));
                return;
            } else{
                map.put(A[i], i);
            }
        }
    }

Time Complexity: O(n) Space Complexity: O(n).

Problem-31

Cho một mảng A gồm n phần tử. Tìm ba phần tử i,j và k trong mảng sao cho $A[i]^2 + A[j]^2=A[k]^2$ ?

Solution:

Sắp xếp mảng đã cho.
Với mỗi phần tử mảng, tôi tính $A[i]^2$ và lưu vào mảng tạm.
Từ đây bài toán tương tự như Problem-27

Time Complexity: Time dành cho sắp xếp + n * (Time cho tìm kiếm tổng) = $O(nlogn) + n* O(n) = n^2$ Space Complexity: O(1).

Problem-32

Tìm hai phần tử có tổng gần bằng 0 nhất: Cho một mảng có cả số dương và số âm, hãy tìm hai phần tử sao cho tổng của chúng gần bằng 0 nhất. Đối với mảng bên dưới, thuật toán sẽ cho -80 và 85. Ví dụ: 1 60 – 10 70 – 80 85

Solution: Brute Force Solution: Đối với mỗi phần tử, tìm tổng với mọi phần tử khác trong mảng và so sánh tổng. Cuối cùng, trả lại số tổng tối thiểu.

    public void TwoElementsWithMinSum(int[] A){
        int i, j, min_sum, sum, min_i, min_j, n = A.length;
        if(n < 2){
            System.out.println("Invalid input");
            return;
        }
        
        min_i = 0;
        min_j = 1;
        min_sum = A[0] + A[1];
        for (i = 0; i < n-1; i++) {
            for (j = 0; j < n; j++) {
                sum = A[i] + A[j];
                if (Math.abs(min_sum) > Math.abs(sum)){
                    min_sum = sum;
                    min_i = i;
                    min_j = j;
                }
            }
        }
        System.out.println("The two elements are " + A[min_i] + " and " + A[min_j]);
    }

Time complexity: $O(n^2)$ . Space Complexity: $O(1)$ .

Problem-33

Chúng ta có thể cải thiện độ phức tạp về thời gian của Problem-32 không?

Solution: Sử dụng sắp xếp

Sắp xếp tất cả các phần tử của mảng đầu vào đã cho.
Duy trì hai chỉ số, một ở đầu (i = 0) và một ở cuối (j = n – 1). Ngoài ra, duy trì hai biến để theo dõi tổng dương nhỏ nhất gần bằng không và tổng âm nhỏ nhất gần bằng không.

While i < j:

Nếu tổng cặp hiện tại là > 0 và < postiveClosest thì hãy cập nhật postiveClosest. Giảm j.

Nếu tổng cặp hiện tại là < 0 và > negativeClosest thì hãy cập nhật negativeClosest. Tăng i.

```
Else, in ra cặp đó.
```

public void TwoElementsWithMinSum(int[] A){
        int n = A.length;
        int i=0, j=n-1, temp, positiveClosest = Integer.MAX_VALUE,
                negativeClosest = Integer.MIN_VALUE;
        Arrays.sort(A);
        while(i<j){
            temp = A[i] + A[j];
            if(temp > 0){
                if(temp < positiveClosest){
                    positiveClosest = temp;
                }
                j--;
            } else if (temp < 0) {
                if (temp > negativeClosest){
                    negativeClosest = temp;
                }
                i++;
            } else {
                System.out.println("Closet Sum: " + A[i] + A[j]);
                return;
            }
        }
        System.out.println(Math.abs(negativeClosest) > positiveClosest
                                ? positiveClosest : negativeClosest);
    }

Time Complexity: $O(nlogn)$ ,
Space Complexity: $O(1)$ .

Problem-34

Cho một mảng gồm n phần tử. Tìm ba phần tử trong mảng sao cho tổng của chúng bằng K?

Solution: Giải pháp mặc định cho vấn đề này là, đối với mỗi 3 phần tử đầu vào, hãy kiểm tra xem tổng bằng K hay không. Điều này chúng ta có thể giải quyết chỉ bằng cách sử dụng ba vòng lặp for đơn giản.

    public void BruteForceSearch(int A[], int n, int data){
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    if(A[i] + A[j] + A[k] == data){
                        System.out.println("Items found i: " + i + " j:" + j + " k:" + k);
                        return;
                    }
                }
            }
        }
        System.out.println("Items not found: No such elements");
    }

Time Complexity: $O(n^3)$ , cho 3 vòng lặp lồng nhau. Space Complexity: O(1).

Problem-35

Giải pháp của Problem-34 có hoạt động ngay cả khi mảng không được sắp xếp không?

Solution: Vì chúng tôi đang kiểm tra tất cả các khả năng, thuật toán đảm bảo rằng chúng tôi có thể tìm thấy ba số có tổng bằng K nếu chúng tồn tại.

Problem-36

Chúng ta có thể sử dụng kỹ thuật sắp xếp để giải quyết Problem-34 không?

Solution: Yes.

    public void Search(int[] A, int data){
        Arrays.sort(A);
        int n = A.length;
        for (int k = 0; k < n; k++) {
            for(int i = k+1, j = n-1; i < j;){
                if(A[k] + A[i] + A[j] == data){
                    System.out.println("Items found i: " + i + " j:" + j + " k:" + k);
                    return;
                } else if(A[k] + A[i] + A[j] < data){
                    i++;
                } else {
                    j--;
                }
            }
        }
        System.out.println("Not found");
    }

Time Complexity: Time dành cho sắp xếp + Time dành cho tìm kiếm trong list đã được sắp xếp $= O(nlogn) + O(n^2) ≈ O(n^2).$
Space Complexity: O(1).

Problem-37

Chúng ta có thể sử dụng hashing để giải quyết Problem-34 không?

Solution: Yes. Vì mục tiêu của chúng ta là tìm ba chỉ mục của mảng có tổng là K. Giả sử các chỉ số đó là X, Y và Z. Điều đó có nghĩa là A[X] + A[Y] + A[Z] = K. Giả sử rằng chúng ta đã giữ tất cả các tổng có thể có cùng với các cặp của chúng trong bảng băm. Điều đó có nghĩa là khóa của bảng băm là K – A[X] và các giá trị cho K – A[X] đều là các cặp đầu vào khả dĩ có tổng bằng nếu K – A[X].

Algorithm:

Trước khi bắt đầu tìm kiếm, hãy thêm tất cả các tổng có thể có với các cặp phần tử vào bảng băm.
Với mỗi phần tử của mảng đầu vào, hãy chèn vào bảng băm. Giả sử phần tử hiện tại là A[X].
Kiểm tra xem có tồn tại trong bảng key hay không: K — A[X].
Nếu phần tử như vậy tồn tại thì quét các cặp phần tử của K – A[X] và trả về tất cả các cặp có thể bằng cách bao gồm cả A[X].
Nếu không có phần tử nào như vậy tồn tại (với khóa K – A[X]) thì chuyển sang phần tử tiếp theo.

Time Complexity: Thời gian để lưu trữ tất cả các cặp có thể có trong bảng Hash + tìm kiếm $= O(n^2) +O(n^2) ≈ O(n^2)$ .
Space Complexity: $O(n)$ .

cấu trúc dữ liệu Thuật toán

Problem-19

Problem-20

Problem-21

Problem-22

Problem-23

Problem-24

Problem-25

Problem-27

Problem-28

Problem-29

Problem-30

Problem-31

Problem-32

Problem-33

Problem-34

Problem-35

Problem-36

Problem-37

Mục lục