Problem-39

Cho A là một dãy gồm n số nguyên phân biệt. Giả sử A có thuộc tính sau: tồn tại chỉ số 1 ≤ k ≤ n sao cho A[1],...,.A[k] là dãy tăng và A[k + 1],...,A[n] là dãy giảm. Thiết kế và phân tích một thuật toán hiệu quả để tìm k.

Solution: Chúng ta sử dụng một biến thể của tìm kiếm nhị phân.

    public int Search(int[] A){
        int mid, first = 0, last = A.length - 1;
        while(first <= last){
            if(first == last){
                return A[first];
            } else if (first == last - 1) {
                return Integer.max(A[first], A[last]);
            } else {
                mid = first + (last - first)/2;
                if(A[mid-1] < A[mid] && A[mid] > A[mid+1]){
                    return A[mid];
                } else if (A[mid-1] < A[mid] && A[mid] < A[mid+1]) {
                    first = mid + 1;
                } else if (A[mid-1] > A[mid] && A[mid] > A[mid+1]) {
                    last = mid - 1;
                } else {
                    return Integer.MIN_VALUE;
                }
            }
        }
    }

Phương trình đệ quy là $T(n) = 2T(n/2) + c$. Sử dụng master theorem, ta nhận được $O(logn)$

Problem-40

Nếu chúng ta không biết kích cỡ n của mảng, làm cách nào để giải Problem-39?

Solution: Liên tục tính A[1],A[2],A[4],A[8],A[16], v.v., cho đến khi tìm được giá trị n sao cho A[n] thỏa mãn yêu cầu. Độ phức tạp của thời gian: $O(logn)$, vì chúng ta đang di chuyển với tốc độ x2.

Problem-41

Đưa ra một mảng đầu vào có kích thước không xác định với tất cả 1 ở đầu và 0 ở cuối. Tìm index trong mảng từ nơi bắt đầu của 0. Hãy xem xét có hàng triệu số 1 và 0 trong mảng. Ví dụ: 1111111………1100000…….0000000.

Solution: Vấn đề này gần giống với Problem-40. Kiểm tra các bit ở tốc độ 2k trong đó k = 0,1,2 .... Vì chúng ta đang di chuyển với tốc độ x2, nên độ phức tạp là $O(logn)$.

Problem-42

Cho một mảng n số nguyên đã được sắp xếp đã được xoay không xác định số lần, hãy đưa ra thuật toán O(logn) để tìm một phần tử trong mảng. Ví dụ: Tìm 5 trong mảng (15 16 19 20 25 1 3 4 5 7 10 14)
Kết quả: 8 (chỉ số của 5 trong mảng)

Solution: Chúng ta hãy giả sử rằng mảng đã cho là A[] và sử dụng giải pháp của Bài toán-39 với phần mở rộng. Hàm bên dưới FindPivot trả về giá trị k (giả sử rằng hàm này trả về chỉ mục thay vì giá trị). Tìm điểm xoay, chia mảng thành hai mảng con và gọi tìm kiếm nhị phân.

Ý tưởng chính để tìm điểm xoay là dành cho một mảng được sắp xếp (theo thứ tự tăng dần) và được xoay vòng, phần tử trục là phần tử duy nhất mà phần tử tiếp theo của nó nhỏ hơn nó. Sử dụng các tiêu chí trên và phương pháp tìm kiếm nhị phân, chúng ta có thể nhận được phần tử trục trong thời gian O(logn).

Algorithm:

1. Tìm ra điểm trục và chia mảng thành hai mảng con.
2. Bây giờ gọi tìm kiếm nhị phân cho một trong hai mảng con.
   • nếu phần tử lớn hơn phần tử đầu tiên thì tìm trong mảng con bên trái b.
   • nếu không tìm trong mảng con bên phải
3. Nếu phần tử được tìm thấy trong mảng con đã chọn thì trả về index, ngược lại trả về –1.

    public int findPivot(int[] A, int start, int finish){
        if(finish - start == 0){
            return start;
        } else if (start == finish-1) {
            if (A[start] >= A[finish]){
                return start;
            } else {
                return finish;
            }
        } else {
            int mid = start + (finish - start)/2;
            if(A[start] >= A[mid]){
                return findPivot(A, start, mid);
            } else {
                return findPivot(A, mid, finish);
            }
        }
    }
    
    public int search(int A[], int n, int x){
        int pivot = findPivot(A, 0, n-1);
        if(A[pivot] == x){
            return pivot;
        }
        if(A[pivot] <= x){
            return binarySearch(A, 0, pivot-1, x);
        } else {
            return binarySearch(A, pivot+1, n-1, x);
        }
    }
    
    public int binarySearch(int A[], int low, int high, int x){
        if(high > low){
            int mid = low + (high - low)/2;
            if(x == A[mid]){
                return mid;
            }
            if (x > A[mid]){
                return binarySearch(A, mid + 1, high, x);
            } else {
                return binarySearch(A, low, mid-1, x);
            }
        }
        return -1;
    }

Time complexity:O(logn).

Problem-43

Chúng ta có thể giải quyết Problem-42 chỉ với 1 lần quét không?

Solution: Yes

    public int search(int[] A, int left, int right, int data){
        if(left > right){
            return -1;
        }
        int mid = left + (right - left)/2;
        if(data == A[mid]){
            return mid;
        } else if (A[left] <= A[mid]) {
            if(data >= A[left] && data < A[mid]){
                return search(A, left, mid-1, data);
            } else {
                return search(A, mid+1, right, data);
            }
        } else {
            if(data > A[mid] && data <= A[right]){
                return search(A, mid+1, right, data);
            } else {
                return search(A, left, mid-1, data);
            }
        }
    }

Time complexity: O(logn). Space complexity: O(logn)

Problem-44

Chúng ta có thể giải Problem-43 mà không cần đệ quy không?

Solution:

    public int search(int A[], int data){
        int left = 0;
        int right = A.length - 1;
        while(left <= right){
            int mid = left + (right - left)/2;
            if(data == A[mid]){
                return mid;
            }

            if (A[left] < A[mid]) {
                if (A[left] <= data && data < A[mid]) {
                    right = mid-1;
                } else {
                    left = mid+1;
                }
            } else if (A[left] > A[mid]) {
                if(A[mid] < data && data <= A[right]){
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            } else {
                left++;
            }
        }
        return -1;
    }

Problem-45

Tìm kiếm bitonic: Một mảng là bitonic nếu nó bao gồm một dãy số nguyên tăng dần theo ngay sau bởi một dãy số nguyên giảm dần. Cho một mảng bitonic A gồm n số nguyên phân biệt, hãy mô tả cách xác định xem một số nguyên đã cho có trong mảng theo các bước O(logn) hay không.

Solution: Giải pháp tương tự như đối với Problem-39

Problem-47

Đưa ra thuật toán O(nlogn) để tính median(trung vị) của dãy n số nguyên.

Solution: Sắp xếp và trả về phần tử ở vị trí n/2.

Problem-48

Cho hai danh sách đã sắp xếp có kích thước m và n, hãy tìm trung vị của tất cả các phần tử trong thời gian O(log (m + n)).

Solution: Mình sẽ trình bày chi tiết trong chương Divide and Conquer.

Problem-49

Cho một mảng A đã sắp xếp gồm n phần tử, có thể trùng lặp, hãy tìm index của lần xuất hiện đầu tiên của một số cho trước trong thời gian O(logn).

Solution: Để tìm lần xuất hiện đầu tiên của một số, chúng ta cần kiểm tra điều kiện sau. Trả lại vị trí nếu bất kỳ điều nào sau đây là đúng:

public int binarySearchFirstOccurrence(int A[], int low, int high, int data){
        if(high >= low){
            int mid = low + (high - low)/2;
            if((mid == low && A[mid] == data) || (A[mid] == data) && A[mid-1] < data){
                return mid;
            } else if (A[mid] >= data) {
                return binarySearchFirstOccurrence(A, low, mid-1, data);
            } else {
                return binarySearchFirstOccurrence(A, mid+1, high, data);
            }
        }
        return -1;
    }

Time Complexity: O(logn).

Problem-50

Cho một mảng A đã sắp xếp gồm n phần tử, có thể trùng lặp, hãy tìm index của lần xuất hiện cuối của một số cho trước trong thời gian O(logn).

Solution: Để tìm lần xuất hiện cuối của một số, chúng ta cần kiểm tra điều kiện sau. Trả lại vị trí nếu bất kỳ điều nào sau đây là đúng:

    public int binarySearchLastOccurrence(int A[], int low, int high, int data){
        if(high >= low){
            int mid = low + (high - low)/2;
            if((mid == high && A[mid] == data) || (A[mid] == data) && A[mid+1] > data){
                return mid;
            } else if (A[mid] <= data) {
                return binarySearchFirstOccurrence(A, mid+1, high, data);
            } else {
                return binarySearchFirstOccurrence(A, low, mid-1, data);
            }
        }
        return -1;
    }

Time Complexity: O(logn).

Problem-51

Cho một mảng n phần tử đã được sắp xếp, có thể trùng lặp. Tìm số lần xuất hiện của một số.

Solution: Brute Force - Thực hiện tìm kiếm tuyến tính của mảng và số gia tăng khi chúng tôi tìm thấy dữ liệu phần tử trong mảng.

public int LinearSearchCount(int[] A, int data){
        int count = 0;
        for (int i = 0; i < A.length; i++) {
            if(A[i] == data){
                count++;
            }
        }
        return count;
    }

Time Complexity: O(n).

Problem-52

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

Solution: Chúng ta có thể giải quyết vấn đề này bằng cách sử dụng tìm kiếm nhị phân, sau đó là một lần quét nhỏ khác.

Algorithm:

• Thực hiện tìm kiếm nhị phân cho dữ liệu trong mảng. Giả sử vị trí của nó là K.
• Bây giờ di chuyển về phía bên trái từ K và đếm số lần xuất hiện của dữ liệu. Để số đếm này là leftCount.
• Tương tự, di chuyển sang phải và đếm số lần xuất hiện của dữ liệu. Để số đếm này là rightCount.

Tổng số lần xuất hiện $= leftCount + 1 + rightCount$

Time Complexity– O(logn + S) trong đó S là số lần xuất hiện của data.

Problem-53

Có cách nào khác để giải quyết Vấn đề-51 không?

Solution:

• Tìm lần xuất hiện đầu tiên của dữ liệu và lấy index của nó là firstOccurrence (đối với thuật toán tham khảo Problem-49)
• Tìm lần xuất hiện cuối cùng của dữ liệu và lấy index của nó là lastOccurrence (đối với thuật toán tham khảo Problem-50)
• Return $lastOccurrence – firstOccurrence + 1$

Time Complexity $= O(logn + logn) =O(logn).$

Problem-54

Số tiếp theo trong dãy 1,11,21 là gì và tại sao?

Solution: Câu này là chơi chữ trong tiếng anh 😀 Đọc to số đã cho. Đây chỉ là một vấn đề thú vị.

Vì vậy, câu trả lời là, số tiếp theo là đại diện của số trước đó bằng cách đọc to nó.

    public String generateNextNumberFromReading(int n){
        StringBuilder str = new StringBuilder("1");
        while(n-- > 1){
            StringBuilder temp = new StringBuilder();
            int count = 1;
            for (int i = 0; i < str.length(); i++) {
                if(str.charAt(i) == str.charAt(i-1)){
                    count++;
                } else {
                    temp.append(count);
                    temp.append(str.charAt(i-1));
                    count = 1;
                }
            }
            temp.append(count);
            temp.append(str.charAt(str.length() - 1));
            str = temp;
        }
        return str.toString();
    }

Problem-55

Tìm số nhỏ thứ hai một cách hiệu quả.

Solution: Bài toán về tìm phần tử lớn hoặc nhỏ thứ k chúng ta nên sử dụng cấu trúc Heap.