Problem-57

Một phần tử chiếm đa số nếu nó xuất hiện hơn n/2 lần. Đưa ra một thuật toán xác định phần tử chiếm đa số trong mảng (nếu nó tồn tại).

Solution: Giải pháp cơ bản là có hai vòng lặp và theo dõi số lượng tối đa cho tất cả các phần tử khác nhau. Nếu số lượng tối đa trở nên lớn hơn n/2, dừng các vòng lặp và trả về phần tử có số lượng tối đa. Nếu số lượng tối đa không vượt quá n/2, thì phần tử đa số không tồn tại.

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

Problem-58

Chúng ta có thể cải thiện độ phức tạp thời gian của Problem-57 thành $O(nlogn)$ không?

Solution: Sử dụng tìm kiếm nhị phân, chúng ta có thể đạt được điều này. Node của Cây tìm kiếm nhị phân (được sử dụng trong phương pháp này) sẽ như sau.

Chèn từng phần tử vào BST và nếu một phần tử đã có mặt thì hãy biến đếm count. Bất cứ khi nào count > n/2 ta được kết quả cần tìm. Phương pháp này hoạt động tốt cho các trường hợp n/2 +1 lần xuất hiện của phần tử đa số xuất hiện ở đầu mảng, ví dụ {1,1,1,1,1,2,3 và 4}.

Time Complexity: Nếu cây binary-search tree được sử dụng thì độ phức tạp ở worst time case sẽ là $O(n^2)$.
Nếu cây balanced-binary-search tree được sử dụng thì $O(nlogn)$.

Space Complexity: O(n).

Problem-59

Có cách nào khác để đạt được độ phức tạp $O(nlogn)$ cho Problem-57 không?

Solution: Sắp xếp mảng đầu vào và quét mảng đã sắp xếp để tìm phần tử đa số.

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

Problem-60

Chúng ta có thể cải thiện độ phức tạp cho Problem-57 không?

Solution: Nếu một phần tử xuất hiện nhiều hơn n/2 lần trong A thì nó phải là trung vị của A. Nhưng, điều ngược lại là không đúng, vì vậy một khi trung vị được tìm thấy, chúng ta phải kiểm tra xem nó xuất hiện bao nhiêu lần trong A. Chúng ta có thể sử dụng lựa chọn tuyến tính mất thời gian $O(n)$ (đối với thuật toán, mình sẽ trình bày chi tiết trong chương Selection Algorithms).

Problem-61

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

Solution: Sử dụng thuật toán bỏ phiếu của Moore

1. Bước đầu tiên đưa ra phần tử có thể là phần tử chiếm đa số trong mảng. Nếu có một phần tử đa số trong một mảng, thì bước này chắc chắn sẽ trả về phần tử đa số, nếu không, nó sẽ trả về ứng cử viên cho phần tử đa số đó.
2. Kiểm tra xem phần tử thu được từ bước trên có phải là phần tử đa số hay không. Bước này là cần thiết vì có thể không có phần tử đa số.

class MajorityElement {
    /* Function to print Majority Element */
    void printMajority(int a[], int size)
    {
        /* Find the candidate for Majority*/
        int cand = findCandidate(a, size);
 
        /* Print the candidate if it is Majority*/
        if (isMajority(a, size, cand))
            System.out.println(" " + cand + " ");
        else
            System.out.println("No Majority Element");
    }
 
    /* Function to find the candidate for Majority */
    int findCandidate(int a[], int size)
    {
        int maj_index = 0, count = 1;
        int i;
        for (i = 1; i < size; i++) {
            if (a[maj_index] == a[i])
                count++;
            else
                count--;
            if (count == 0) {
                maj_index = i;
                count = 1;
            }
        }
        return a[maj_index];
    }
 
    /* Function to check if the candidate occurs more
       than n/2 times */
    boolean isMajority(int a[], int size, int cand)
    {
        int i, count = 0;
        for (i = 0; i < size; i++) {
            if (a[i] == cand)
                count++;
        }
        if (count > size / 2)
            return true;
        else
            return false;
    }
 
    /* Driver code */
    public static void main(String[] args)
    {
        MajorityElement majorelement
            = new MajorityElement();
        int a[] = new int[] { 1, 3, 3, 1, 2 };
       
        // Function call
        int size = a.length;
        majorelement.printMajority(a, size);
    }
}

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

Problem-62

Cho một mảng gồm 2n phần tử, trong đó có n phần tử giống nhau và n phần tử còn lại khác nhau. Tìm phần tử đa số

Solution: Các phần tử được lặp lại sẽ chiếm một nửa mảng. Bất kể đó là sự sắp xếp nào, chỉ một trong những điều dưới đây sẽ đúng:

• Tất cả các phần tử trùng lặp sẽ ở khoảng cách tương đối là 2 với nhau. Ví dụ: n , 1, n , 100, n , 54, n ...
• Ít nhất hai phần tử trùng lặp sẽ nằm cạnh nhau.

Ex: n,n, 1,100, n, 54, n,....
n, 1,n,n,n,54,100...
1,100,54, n,n,n,n....

Trong trường hợp xấu nhất, chúng ta sẽ cần hai lần duyệt qua mảng:

• Lần 1: so sánh A[i] và A[i + 1]
• Lần 2: so sánh A[i] và A[i + 2]

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

Problem-63

Cho một mảng có 2n + 1 phần tử số nguyên, n phần tử xuất hiện hai lần ở các vị trí tùy ý trong mảng và một số nguyên duy nhất chỉ xuất hiện một lần ở đâu đó bên trong. Tìm số nguyên đó với phép toán O(n) và bộ nhớ phụ O(1).

Solution: Ngoại trừ một phần tử, tất cả các phần tử được lặp lại. Chúng ta biết rằng A XOR A = 0. Dựa trên điều này, nếu chúng ta XOR tất cả các phần tử đầu vào thì chúng ta sẽ nhận được phần tử còn lại.

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

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

Problem-64

Ném trứng từ tòa nhà n tầng: Giả sử chúng ta có một tòa nhà n tầng và một số quả trứng. Cũng giả định rằng một quả trứng sẽ vỡ nếu nó được ném từ tầng F trở lên, và sẽ không vỡ nếu không. Lên chiến lược xác định tầng F, đồng thời phá trứng O(logn).

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

Problem-65

Tìm tối thiểu cục bộ của một mảng: Ta nói rằng một phần tử arr[x] là phần tử tối thiểu cục bộ nếu nó nhỏ hơn cả hai phần tử lân cận của nó.

Solution:

class GFG
{
     
    // A binary search based function that returns
    // index of a local minima.
    public static int localMinUtil(int[] arr, int low,
                                   int high, int n)
    {
         
        // Find index of middle element
        int mid = low + (high - low) / 2;
         
         // Compare middle element with its neighbours
        // (if neighbours exist)
        if(mid == 0 || arr[mid - 1] > arr[mid] && mid == n - 1 ||
           arr[mid] < arr[mid + 1])
                return mid;
         
        // If middle element is not minima and its left
        // neighbour is smaller than it, then left half
        // must have a local minima.
        else if(mid > 0 && arr[mid - 1] < arr[mid])
                return localMinUtil(arr, low, mid - 1, n);
         
        // If middle element is not minima and its right
        // neighbour is smaller than it, then right half
        // must have a local minima.
        return localMinUtil(arr, mid + 1, high, n);
    }
     
    // A wrapper over recursive function localMinUtil()
    public static int localMin(int[] arr, int n)
    {
        return localMinUtil(arr, 0, n - 1, n);
    }
     
     
    public static void main (String[] args)
    {
         
        int arr[] = {4, 3, 1, 14, 16, 40};
        int n = arr.length;
        System.out.println("Index of a local minima is " + localMin(arr, n));
    
    }
}

Problem-66

Cho một mảng n × n phần tử sao cho mỗi hàng theo thứ tự tăng dần và mỗi cột theo thứ tự tăng dần, hãy lập thuật toán O(n) để xác định xem phần tử x đã cho có trong mảng hay không. Giả sử rằng tất cả các phần tử trong mảng n × n là khác nhau.

Solution: Ý tưởng đơn giản là loại bỏ một hàng hoặc cột trong mỗi phép so sánh cho đến khi tìm thấy một phần tử.
Bắt đầu tìm kiếm từ góc trên bên phải của ma trận.

1. Số đã cho lớn hơn số hiện tại : Điều này sẽ đảm bảo rằng tất cả các phần tử trong hàng hiện tại đều nhỏ hơn số đã cho vì con trỏ đã ở phần tử ngoài cùng bên phải và hàng được sắp xếp. Do đó, toàn bộ hàng bị loại bỏ và tiếp tục tìm kiếm hàng tiếp theo. Ở đây, loại bỏ có nghĩa là không cần tìm kiếm một hàng.
2. Số đã cho bé hơn số hiện tại: Điều này sẽ đảm bảo rằng tất cả các phần tử trong cột hiện tại đều lớn hơn số đã cho. Do đó, toàn bộ cột bị loại bỏ và tiếp tục tìm kiếm cột trước đó, tức là cột ngay bên trái.
3. Số đã cho bằng số hiện tại: Kết thúc tìm kiếm

Thuật toán và code mình tham khảo ở đây.

class GFG {
 
    /* Searches the element x in mat[][]. If the
    element is found, then prints its position
    and returns true, otherwise prints "not found"
    and returns false */
    private static void search(int[][] mat, int n, int x)
    {
 
        // set indexes for top right
        int i = 0, j = n - 1;
        // element
 
        while (i < n && j >= 0) {
            if (mat[i][j] == x) {
                System.out.print("Element found at " + i
                                 + " " + j);
                return;
            }
            if (mat[i][j] > x)
                j--;
            else // if mat[i][j] < x
                i++;
        }
 
        System.out.print("n Element not found");
        return; // if ( i==n || j== -1 )
    }
    // Driver code
    public static void main(String[] args)
    {
        int mat[][] = { { 10, 20, 30, 40 },
                        { 15, 25, 35, 45 },
                        { 27, 29, 37, 48 },
                        { 32, 33, 39, 50 } };
 
        // Function call
        search(mat, 4, 29);
    }
}

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

Problem-68

Cho ma trận n × n và trong mỗi hàng, tất cả các số 1 được theo sau bởi các số 0. Tìm hàng có nhiều chữ số 0 nhất.

Solution: Bắt đầu với hàng đầu tiên, cột cuối cùng. Nếu phần tử là 0 thì di chuyển đến cột trước đó trong cùng một hàng và đồng thời tăng bộ đếm để chỉ ra số lượng 0 tối đa. Nếu phần tử là 1 thì di chuyển đến hàng tiếp theo trong cùng một cột. Lặp lại quá trình này cho đến khi bạn đến hàng cuối cùng, cột đầu tiên.

Time Complexity: $O(2n) ≈ O(n)$

Problem-69

Đưa ra một mảng đầu vào có kích thước không xác định, với tất cả các số ở đầu và các ký hiệu đặc biệt ở cuối. Tìm index trong mảng từ nơi các ký hiệu đặc biệt bắt đầu.

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

Problem-70

Tách số chẵn và số lẻ: Cho mảng A[], viết hàm tách số chẵn và số lẻ. Các chức năng nên đặt tất cả các số chẵn trước, sau đó là các số lẻ.

Example: Input = {12,34,45,9,8,90,3} Output = {12,34,90,8,9,45,3}

Note: Ở đầu ra, thứ tự các số có thể thay đổi, tức là, trong ví dụ trên, 34 có thể đứng trước 12 và 3 có thể đứng trước 9.

Solution: Vấn đề rất giống với Tách 0 và 1 (Tách chẵn lẻ chỉ khác điều kiện %2 == 0 hay không) trong một mảng và cả hai vấn đề đều là biến thể của vấn đề quốc kỳ Hà Lan nổi tiếng.

Logic tương tự như Quick sort.

1. Khởi tạo 2 biến chứa index left và right: left = 0, right = n – 1
2. Tiếp tục tăng left index cho đến khi chúng ta thấy một số lẻ.
3. Tiếp tục giảm right index cho đến khi chúng ta thấy một số chẵn.
4. Nếu left < right thì hoán đổi A[left] và A[right]

public class Segregate 
{
    /*Function to put all 0s on left and all 1s on right*/
    void segregate0and1(int arr[], int size) 
    {
        /* Initialize left and right indexes */
        int left = 0, right = size - 1;
  
        while (left < right) 
        {
            /* Increment left index while we see 0 at left */
            while (arr[left] == 0 && left < right)
               left++;
  
            /* Decrement right index while we see 1 at right */
            while (arr[right] == 1 && left < right)
                right--;
  
            /* If left is smaller than right then there is a 1 at left
               and a 0 at right.  Exchange arr[left] and arr[right]*/
            if (left < right) 
            {
                arr[left] = 0;
                arr[right] = 1;
                left++;
                right--;
            }
        }
    }
      
    /* Driver Program to test above functions */
    public static void main(String[] args) 
    {
        Segregate seg = new Segregate();
        int arr[] = new int[]{0, 1, 0, 1, 1, 1};
        int i, arr_size = arr.length;
  
        seg.segregate0and1(arr, arr_size);
  
        System.out.print("Array after segregation is ");
        for (i = 0; i < 6; i++)
            System.out.print(arr[i] + " ");
    }
}

Problem-71

Sau đây là một cách khác để cấu trúc Bài toán-70, nhưng có một chút khác biệt. Tách các số 0 và 1 trong một mảng: Chúng ta được cung cấp một mảng 0 và 1 theo thứ tự ngẫu nhiên. Tách các số 0 ở bên trái và 1 ở bên phải của mảng. Duyệt qua mảng chỉ một lần.

Input array = [0,1,0,1,0,0,1,1,1,0]
Output array = [0,0,0,0,0,1,1,1,1,1]

Solution: Đếm 0 và 1

1. Đếm số 0. Đặt số đếm là C.
2. Khi chúng ta đã đếm được, hãy đặt C 0 ở đầu và 1 ở vị trí n-C còn lại trong mảng.

Time Complexity: O(n).

Problem-73

Sắp xếp một mảng gồm 0, 1 và 2. Cho một mảng A[] bao gồm các số 0, 1 và 2, hãy đưa ra thuật toán để sắp xếp A[]. Thuật toán nên đặt tất cả các số 0 trước, sau đó là tất cả các số 1 và cuối cùng là tất cả các số 2 ở cuối.
Ví dụ Đầu vào = {0,1,1,0,1,2,1,2,0,0,0,1}, Đầu ra = {0,0,0,0,0,1,1,1,1, 1,2,2}

Solution: Code tương tự Problem-70

    public void Sorting012sDutchFlagProblem(int A[]){
        int low = 0, mid = 0, high = A.length-1;
        while (mid < high){
            switch (A[mid]){
                case 0:
                    swap(A[low], A[mid]);
                    low++; mid++;
                    break;
                case 1:
                    mid++;
                    break;
                case 2:
                    swap(A[mid], A[high]);
                    high--;
                    break;
            }
        }
    }

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

Problem-74

Chênh lệch tối đa giữa hai phần tử: Cho một mảng A[] gồm các số nguyên, hãy tìm sự khác biệt giữa hai phần tử bất kỳ sao cho phần tử lớn hơn xuất hiện sau số nhỏ hơn trong A[].

Ví dụ: Nếu mảng là [2,3,10,6,4,8,1] thì giá trị trả về phải là 8 (Sự khác biệt giữa 10 và 2).
Nếu mảng là [ 7,9,5,6,3,2 ] thì giá trị trả về phải là 2 (Sự khác biệt giữa 7 và 9)

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

Problem-75

Cho một mảng gồm 101 phần tử. Trong số 101 phần tử, 25 phần tử được lặp lại 2 lần, 12 phần tử được lặp lại 4 lần và một phần tử được lặp lại 3 lần. Tìm phần tử lặp lại 3 lần trong O(n).

Solution: Trước khi giải quyết vấn đề này, chúng ta hãy xem xét thuộc tính phép toán XOR sau: $a XOR a = 0$.

Algorithm:

• XOR tất cả các phần tử của mảng đã cho và giả sử kết quả là A.
• Sau thao tác này, 2 lần xuất hiện của số xuất hiện 3 lần trở thành 0 và một lần xuất hiện còn lại giữ nguyên.
• 12 phần tử xuất hiện 4 lần trở thành 0.
• 25 phần tử xuất hiện 2 lần trở thành 0.
• Vì vậy, chỉ XOR tất cả các phần tử sẽ cho kết quả.

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

Problem-76

Cho một số n, hãy đưa ra thuật toán tìm số các số 0 ở cuối trong n!.

Solution:

1. Một phương pháp đơn giản là trước tiên tính giai thừa của n, sau đó đếm các số 0 ở cuối kết quả (Chúng ta có thể đếm các số 0 ở cuối bằng cách chia nhiều lần giai thừa cho 10 cho đến khi phần còn lại khác 0).
2. Phương pháp trên có thể gây tràn bộ nhớ đối với các số lớn hơn một chút vì giai thừa của một số khi tăng lên là một số rất lớn. Ý tưởng là xét các thừa số nguyên tố của một giai thừa n. Một số 0 ở cuối luôn được tạo ra bởi các thừa số nguyên tố 2 và 5. Nếu chúng ta có thể đếm số lượng 5 và 2, nhiệm vụ của chúng ta đã hoàn thành. Hãy xem xét các ví dụ sau đây. n = 5: Có 1 số 5 và 3 số 2 là thừa số nguyên tố của 5! $(2*2*2*3*5)$. Vì vậy, số lượng các số 0 ở cuối là 1. n = 11: Có hai số 5 và tám số 2 ở thừa số nguyên tố là 11! $(2^8*3^4*5^2*7)$. Vậy số lượng các số 0 ở cuối là 2.
3. Ta dễ dàng nhận thấy số các số 2 trong các thừa số nguyên tố luôn lớn hơn hoặc bằng số các số 5. Vì vậy, nếu chúng ta đếm 5s theo thừa số nguyên tố, thì chúng ta đã hoàn thành. Làm thế nào để đếm tổng số 5 thừa số nguyên tố của n!? Một cách đơn giản là tính floor(n/5). Ví dụ, 7! có một 5, 10! có hai số 5. Tính toán tới đây vẫn chưa xong, có một điều nữa để xem xét. Các số như 25, 125, v.v. có nhiều hơn một số 5. Ví dụ: nếu chúng ta xem xét 28! chúng ta có thêm một số 5 và số lượng số 0 trở thành 6. Xử lý điều này rất đơn giản, đầu tiên, chia n cho 5 và loại bỏ tất cả 5 đơn lẻ, sau đó chia cho 25 để loại bỏ 5 thừa, v.v. Sau đây là công thức tóm tắt để đếm các số 0 ở cuối.

Các chữ số 0 ở sau n! = Số lượng số 5 thừa số nguyên tố của n!
$= floor(n/5) + floor(n/25) + floor(n/125) + ....$

    public  static int NumberOfTrailingZeroNumber(int n){
        int i, count = 0;
        if(n < 0){
            return -1;
        }
        for (i = 5; n/i > 0 ; i *= 5) {
            count += n/i;
        }
        return count;
    }

Time Complexity: O(logn).

Problem-77

Cho một mảng gồm 2n số nguyên theo định dạng sau a1 a2 a3 ...an b1 b2 b3 ...bn. Xáo trộn mảng thành a1 b1 a2 b2 a3 b3 ... an bn mà không có bất kỳ bộ nhớ bổ sung.

Solution: Một giải pháp brute force bao gồm hai vòng lặp lồng nhau để xoay các phần tử trong nửa sau của mảng sang trái. Vòng lặp đầu tiên chạy n lần để bao gồm tất cả các phần tử trong nửa sau của mảng. Vòng lặp thứ hai xoay các phần tử sang trái. Lưu ý rằng start index trong vòng lặp thứ hai phụ thuộc vào phần tử chúng ta đang xoay và end index phụ thuộc vào số lượng vị trí chúng ta cần di chuyển sang trái.

Code tác giả viết khá ngắn gọn, nhiều biến hơi khó đọc, mình thêm in ra ở từng vòng lặp chạy, các bạn khi run nhìn vào kết quả sẽ dễ hình dung hơn.

    public static void main(String[] args) {
        ShuffleArray();
    }

    static void ShuffleArray() {
        int n = 4, A[] = {1, 3, 5, 7, 2, 4, 6, 8};
        for (int i = 0, q = 1, k = n;
             i < n;
             i++, k++, q++) {

            for (int j = k; j > i + q; j--) {
                int temp = A[j - 1];
                A[j - 1] = A[j];
                A[j] = temp;
                print(A);

            }
        }
        print(A);
    }

    static void print(int A[]){
        for (int i = 0; i < A.length; i++) {
            System.out.print(A[i] + " ");
        }
        System.out.println();
    }

Problem-78

Chúng ta có thể cải thiện giải pháp Problem-77 không?

Solution: Chi tiết mình sẽ trình bày trong chương Divide and Conquer. Một giải pháp tốt hơn về độ phức tạp thời gian O(nlogn) có thể đạt được bằng cách sử dụng kỹ thuật Divide and Conquer. Chúng ta hãy xem xét một ví dụ

1. Bắt đầu với mảng: a1 a2 a3 a4 b1 b2 b3 b4
2. Chia mảng thành hai nửa: a1 a2 a3 a4 : b1 b2 b3 b4
3. Trao đổi các phần tử xung quanh trung tâm: trao đổi a3 a4 với b1 b2 và bạn nhận được: a1 a.2 b1 b2 a3 a4 b3 b4
4. Chia a1 a2 b1 b2 thành a1 a2 : b1 b2. Sau đó chia a3 a4 b3 b4 thành a3 a4 : b3 b4
5. Trao đổi các phần tử xung quanh trung tâm cho mỗi mảng con bạn nhận được: a1 b1 a2 b2 và a3 b3 a4 b4

Lưu ý rằng giải pháp này chỉ xử lý trường hợp khi $n = 2^i$ trong đó i = 0,1,2,3, v.v. Trong ví dụ của chúng ta, $n = 2^2 = 4$, điều này giúp dễ dàng phân chia đệ quy mảng thành hai nửa. Ý tưởng cơ bản đằng sau việc tráo đổi các phần tử quanh tâm trước khi gọi hàm đệ quy là tạo ra các bài toán có kích thước nhỏ hơn. Một giải pháp với độ phức tạp thời gian tuyến tính có thể đạt được nếu các phần tử có tính chất cụ thể. Ví dụ: nếu bạn có thể tính toán vị trí mới của phần tử bằng cách sử dụng giá trị của chính phần tử đó. Đây không là gì ngoài kỹ thuật hashing.

Problem-79

Cho một mảng A[], tìm j – i lớn nhất sao cho A[j] > A[i]. Ví dụ, Đầu vào: {34, 8, 10, 3, 2, 80, 30, 33, 1} và Đầu ra: 6 (j = 7, i = 1).

Solution: Brute Force: Trong vòng lặp bên ngoài, chọn từng phần tử một từ bên trái. Trong vòng lặp bên trong, so sánh phần tử được chọn với các phần tử bắt đầu từ phía bên phải. Dừng vòng lặp bên trong khi bạn thấy một phần tử lớn hơn phần tử được chọn và tiếp tục cập nhật j – i tối đa cho đến nay.

    public int maxIndexDiff(int[] A){
        int maxDiff = -1;
        for (int i = 0; i < A.length; i++) {
            for (int j = A.length-1; j > i; j--) {
                if(A[j] > A[i] && maxDiff < (j-i)){
                    maxDiff = j-i;
                }
            }
        }
        return maxDiff;
    }

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

Problem-80

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

Solution: Để giải quyết vấn đề này, chúng ta cần lấy hai chỉ số tối ưu của A[]: left index i và right index j. Đối với phần tử A[i], ta không cần xét A[i] cho left index nếu có phần tử nhỏ hơn A[i] ở vế trái của A[i]. Đối với phần tử A[i], ta không cần xét A[i] cho left index nếu có phần tử nhỏ hơn A[i] ở vế trái của A[i]. Tương tự, nếu có phần tử lớn hơn ở vế phải của A[j] thì ta không cần xét j này cho right index.

Vì vậy, chúng ta xây dựng hai Mảng phụ LeftMins[] và RightMaxs[] sao cho LeftMins[i] giữ phần tử nhỏ nhất ở phía bên trái của A[i] bao gồm A[i] và RightMaxs[j] giữ phần tử lớn nhất ở bên phải cạnh của A[j] kể cả A[j]. Sau khi xây dựng xong hai mảng phụ này, chúng ta duyệt cả hai mảng này từ trái sang phải.

Khi duyệt qua LeftMins[] và RightMaxs[], nếu chúng ta thấy rằng LeftMins[i] lớn hơn RightMaxs[j], thì chúng ta phải di chuyển tiếp trong LeftMins[] (hoặc thực hiện i++) vì tất cả các phần tử ở bên trái của LeftMins[i ] lớn hơn hoặc bằng LeftMins[i]. Nếu không, chúng ta phải tiếp tục trong RightMaxs[j] để tìm giá trị j – i lớn hơn.

Ví dụ: Có mảng sau: [7 3 1 8 9 10 4 5 6]
maxRight là gì?
Điền từ bên phải, 6 là phần tử đầu tiên, tiếp theo 6 > 5, vì vậy một lần nữa chúng ta điền 6 cho đến khi đạt 10 > 6
[10 10 10 10 10 10 6 6 6] đây là maxR
[7 3 1 1 1 1 1 1 1 ] đây là minL

Bây giờ chúng ta thấy rằng làm thế nào để đạt được câu trả lời từ những điều này và bằng chứng cho thấy nó đúng !!!
Hãy so sánh các phần tử đầu tiên của mảng bây giờ chúng ta thấy 10 > 7, bây giờ chúng ta tăng maxR thêm 1 cho đến khi nó nhỏ hơn 7, tức là ở index 5, do đó câu trả lời cho đến hiện tại là j-i=5-0 = 5.
bây giờ chúng ta sẽ tăng minL, chúng ta nhận được 3 nhỏ hơn 6, vì vậy chúng ta tăng maxR cho đến khi đạt đến chỉ số cuối cùng và câu trả lời trở thành j-i=8-1= 7.

chúng ta sẽ xem làm thế nào chúng ta đang nhận được câu trả lời đúng.
Vì chúng ta cần sự khác biệt tối đa j – i sao cho A[i]<= A[j], do đó chúng ta không cần xem xét phần tử sau chỉ số j và phần tử trước chỉ số i.
Tạo 2 mảng maxRight và minLeft.
Đầu tiên, ta sẽ lưu trữ phần tử xuất hiện nhỏ nhất trước phần tử phần tử đang được xét.(MinLeft)
Thứ hai, sẽ lưu trữ phần tử xuất hiện lớn nhất phía sau phần tử đang được xét.(MaxRight)\

Duyệt qua mảng Thứ hai, cho đến khi phần tử trong mảng thứ hai lớn hơn hoặc bằng mảng Thứ nhất và lưu trữ chênh lệch chỉ số. Và nếu nó nhỏ hơn, hãy duyệt qua mảng đầu tiên cho đến khi nó trở nên lớn hơn. Và lưu trữ chênh lệch tối đa của chênh lệch chỉ số này ta sẽ được kết quả.

Code mình có tham khảo ở đây

public class FindMaximum {
    /* Utility Functions to get max and minimum of two integers */
    int max(int x, int y)
    {
        return x > y ? x : y;
    }
 
    int min(int x, int y)
    {
        return x < y ? x : y;
    }
 
    /* For a given array arr[], returns the maximum j-i such that
       arr[j] > arr[i] */
    int maxIndexDiff(int arr[], int n)
    {
        int maxDiff;
        int i, j;
 
        int RMax[] = new int[n];
        int LMin[] = new int[n];
 
        /* Construct LMin[] such that LMin[i] stores the minimum value
           from (arr[0], arr[1], ... arr[i]) */
        LMin[0] = arr[0];
        for (i = 1; i < n; ++i)
            LMin[i] = min(arr[i], LMin[i - 1]);
 
        /* Construct RMax[] such that RMax[j] stores the maximum value
           from (arr[j], arr[j+1], ..arr[n-1]) */
        RMax[n - 1] = arr[n - 1];
        for (j = n - 2; j >= 0; --j)
            RMax[j] = max(arr[j], RMax[j + 1]);
 
        /* Traverse both arrays from left to right to find optimum j - i
           This process is similar to merge() of MergeSort */
        i = 0;
        j = 0;
        maxDiff = -1;
        while (j < n && i < n) {
            if (LMin[i] <= RMax[j]) {
                maxDiff = max(maxDiff, j - i);
                j = j + 1;
            }
            else
                i = i + 1;
        }
 
        return maxDiff;
    }
 
    /* Driver program to test the above functions */
    public static void main(String[] args)
    {
        FindMaximum max = new FindMaximum();
        int arr[] = { 9, 2, 3, 4, 5, 6, 7, 8, 18, 0 };
        int n = arr.length;
        int maxDiff = max.maxIndexDiff(arr, n);
        System.out.println(maxDiff);
    }
}

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

Problem-81

Cho một mảng các phần tử, làm cách nào để bạn kiểm tra xem danh sách có được sắp xếp theo cặp hay không? Một danh sách được coi là sắp xếp theo cặp nếu mỗi cặp số liên tiếp được sắp xếp theo thứ tự (không giảm dần).

Solution:

    public boolean isPairwiseSorted(int[] A){
        if(A.length == 0 || A.length == 1){
            return true;
        }
        for (int i = 0; i < A.length - 1; i=i+2) {
            if(A[i] > A[i+1]){
                return false;
            }
        }
        return true;
    }

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

Problem-82

Cái nào nhanh hơn và bằng bao nhiêu, tìm kiếm tuyến tính chỉ 1000 phần tử trên máy tính 5GHz hoặc tìm kiếm nhị phân 1 triệu phần tử trên máy tính 1 GHz. Giả sử rằng việc thực thi mỗi lệnh trên máy tính 5 GHz nhanh hơn năm lần so với trên máy tính 1 GHz và mỗi lần lặp lại thuật toán tìm kiếm tuyến tính nhanh gấp đôi so với mỗi lần lặp lại thuật toán tìm kiếm nhị phân.

Solution: Tìm kiếm nhị phân trong 1 triệu phần tử sẽ yêu cầu $log _ { 2 } ^ { 1 , 0 0 0 , 0 0 0 }$ hoặc tối đa khoảng 20 lần tìm kiếm (nghĩa là trường hợp xấu nhất). Một tìm kiếm tuyến tính trong 1000 phần tử sẽ yêu cầu 500 lần tìm kiếm (giả sử trong trường hợp trung bình) (nghĩa là đi được một nửa mảng). Do đó, tìm kiếm nhị phân sẽ nhanh hơn $\frac { 5 0 0 } { 2 0 } = 25$ (về số lần tìm kiếm) so với tìm kiếm tuyến tính. Tuy nhiên, do các lần lặp lại tìm kiếm tuyến tính nhanh gấp đôi, nên tìm kiếm nhị phân sẽ nhanh hơn khoảng $\frac { 25 } { 2 } = 12$ lần so với tìm kiếm tuyến tính nói chung, trên cùng một máy.
Vì chúng ta chạy chúng trên các máy khác nhau, trong đó lệnh trên máy 5-GhZ nhanh hơn 5 lần so với lệnh trên máy 1 GHz, tìm kiếm nhị phân sẽ nhanh hơn khoảng $\frac { 12 } { 5 } = 2$ lần so với tìm kiếm tuyến tính! Ý tưởng chính là cải tiến phần mềm có thể làm cho thuật toán chạy nhanh hơn nhiều mà không cần phải sử dụng phần cứng mạnh hơn.