Tìm một dãy được sắp xếp có kích thước 4 trong một mảng trong thời gian tuyến tính

Question

Chúng tôi được cung cấp một dãy số và chúng tôi muốn tìm một dãy số 4 được sắp xếp theo thứ tự tăng dần.

for eg ARRAY    : -4 2 8 3 1 5 
sorted subsequence of size 4 : -4 2 3 5 

PS: Có cách tìm thứ tự sắp xếp có kích thước 3 (see this). Tôi đang cố gắng để suy nghĩ dọc theo cùng một dòng nhưng dường như không thể tìm thấy một giải pháp cho 4 số nguyên.

Answer 1

Đây là giải pháp sẽ tìm thấy một chuỗi được sắp xếp có kích thước cố định k+1 bằng cách thực hiện k truyền qua đầu vào. Mỗi đường chuyền được thực hiện từ trái qua phải.

Vượt qua 1: Tạo mảng phụ p1[0..n-1]. p1[i] nên lưu trữ chỉ mục j của một số nhỏ hơn arr[i] và nằm ở bên trái của arr[i] (nói cách khác: j<i và arr[j]<arr[i]). p1[i] phải chứa -1 nếu không có yếu tố như vậy. (p1 giống với mảng smaller từ giải pháp cho kích thước 3).

Vượt qua 2: Tạo mảng phụ p2[0..n-1]. p2[i] nên lưu trữ chỉ mục j của một số nhỏ hơn arr[i], nằm ở bên trái của arr[i] và như vậy p1[j] != -1 (nói cách khác: j<i, arr[j]<arr[i] và p1[j]!=-1). p2[i] phải chứa -1 nếu không có yếu tố như vậy.

....

Chuyển k: Tạo mảng phụ pk[0..n-1]. pk[i] nên lưu trữ chỉ mục j của một số nhỏ hơn arr[i], nằm ở bên trái của arr[i] và sao cho p(k-1)[j] != -1 (nói cách khác: j<i, arr[j]<arr[i] và p(k-1)[j]!=-1). pk[i] phải chứa -1 nếu không có yếu tố như vậy.

Sau đèo k, mỗi phần tử trong đó pk[i] != -1 tương ứng với phần tử lớn nhất trong một hậu tố được sắp xếp có kích thước k+1.

Mã giả cho ngày qua k (k> 1):

function do_kth_pass(pk[], p_k_minus_1[]) 
    min = -1 
    for i in 0..n-1: 
     if min != -1 and arr[i] > arr[min]: 
      pk[i] = min 
     else 
      pk[i] = -1 
     if p_k_minus_1[i] != -1 and (min == -1 or arr[i] < arr[min]): 
      min = i 

Ví dụ:

Index: 0 1 2 3 4 5 
Array: -4 2 8 3 1 5 
p1:  -1 0 0 0 0 0 
p2:  -1 -1 1 1 -1 4 
p3:  -1 -1 -1 -1 -1 3 

Sau 3 đèo, bạn có p3 [5] = -1, do đó, một dãy được sắp xếp kích thước 4 tồn tại. Các chỉ số của các yếu tố của nó là: p1[p2[p3[5]]], p2[p3[5]], p3[5], 5 đó là 0,1,3,5

Answer 2

Tạo một mảng smaller và greater, tương tự như những gì đã được thực hiện cho một dãy kích thước 3. Thêm vào đó, cũng có betweenSmallerAndCurrent mảng lưu trữ chỉ mục của một giá trị nằm giữa phần tử nhỏ nhất và phần tử hiện tại - cả về giá trị và chỉ mục. Rõ ràng hơn:

betweenSmallerAndCurrent[i] = -1 or 

input[smaller[i]] < input[betweenSmallerAndCurrent[i]] < input[value[i]] and 
smaller[i] < betweenSmallerAndCurrent[i] < value[i] 

Việc xây dựng nên dễ dàng hơn.

Bạn chỉ cần trả lại chỉ mục i trong đó betweenSmallerAndCurrent[i], smaller[betweenSmallerAndCurrent[i]] và greater[i] đều được khởi tạo. Lưu ý rằng chúng tôi không thể chỉ cần kiểm tra smaller[i] vì chúng tôi có thể có một cái gì đó như [2,3,1,4,5], trong trường hợp này, khi chúng tôi nhận được 4, giá trị nhỏ nhất thứ hai 3 trước giá trị nhỏ nhất hiện tại 1.

Ví dụ:

Indices: 0 1 2 3 4 5 6 7 
Input: 12 11 10 5 6 2 9 30 

smaller: -1 -1 -1 -1 3 -1 5 5 
betweenSmallerAndCurrent: 
     -1 -1 -1 -1 -1 -1 4 4 

greater: 7 7 7 7 7 7 7 -1 

Chỉ số duy nhất với tất cả các giá trị khởi tạo là 6 (đầu vào giá trị 9). đang

Java: (không thử nghiệm rộng rãi)

void find4Numbers(int arr[], int n) 
{ 
    int max = n-1; //Index of maximum element from right side 
    int min = 0, second = -1; //Index of minimum element from left side 
    int i; 

    // Create an array that will store index of a smaller 
    // element on left side. If there is no smaller element 
    // on left side, then smaller[i] will be -1. 
    int[] smaller = new int[n]; 
    int[] betweenSmallerAndCurrent = new int[n]; 
    smaller[0] = -1; // first entry will always be -1 
    betweenSmallerAndCurrent[0] = -1; 
    for (i = 1; i < n; i++) 
    { 
     if (arr[i] <= arr[min]) 
     { 
      min = i; 
      smaller[i] = -1; 
      betweenSmallerAndCurrent[i] = -1; 
     } 
     else 
     { 
      smaller[i] = min; 
      if (second != -1 && arr[second] < arr[i]) 
      betweenSmallerAndCurrent[i] = second; 
      else 
      betweenSmallerAndCurrent[i] = -1; 
      if (second == -1 || arr[i] < arr[second]) 
      second = i; 
     } 
    } 

    // Create another array that will store index of a 
    // greater element on right side. If there is no greater 
    // element on right side, then greater[i] will be -1. 
    int[] greater = new int[n]; 
    greater[n-1] = -1; // last entry will always be -1 
    for (i = n-2; i >= 0; i--) 
    { 
     if (arr[i] >= arr[max]) 
     { 
      max = i; 
      greater[i] = -1; 
     } 
     else 
      greater[i] = max; 
    } 

    // Make sure they're right 
    System.out.println(Arrays.toString(smaller)); 
    System.out.println(Arrays.toString(betweenSmallerAndCurrent)); 
    System.out.println(Arrays.toString(greater)); 

    // Now find a number which has both a greater number on 
    // right side and smaller number on left side 
    for (i = 0; i < n; i++) 
    { 
     if (betweenSmallerAndCurrent[i] != -1 && smaller[betweenSmallerAndCurrent[i]] != -1 && greater[i] != -1) 
     { 
      System.out.printf("%d %d %d %d\n", 
          arr[smaller[betweenSmallerAndCurrent[i]]], 
          arr[betweenSmallerAndCurrent[i]], 
          arr[i], 
          arr[greater[i]]); 
      return; 
     } 
    } 

    // If we reach number, then there are no such 3 numbers 
    System.out.println("No such triplet found"); 
} 

Bạn có thể nhận thấy rằng những thay đổi mã chính từ this, ngoài C để chuyển đổi Java và khởi tạo thêm, nằm trong vòng lặp mà thiết lập smaller. Mã nên khá dễ hiểu - hãy thử dịch nó thành các từ nếu bạn gặp rắc rối.

Test.

Answer 3

Có mảng lớn hơn và nhỏ hơn là một lựa chọn tốt nhưng nó làm tăng độ phức tạp của không gian. Dưới đây, là một giải pháp để tìm bốn số trong một chuỗi tuyến tính mà không có không gian mảng bổ sung mà là nó sử dụng không gian cố định và chỉ có một số vượt qua mảng.

#include<iostream> 
using namespace std; 


int sortedSubseqFour(int a[], int n) 
{ 
    int small = INT_MAX; 
    int middle_1 = INT_MAX; 
    int middle_2 = INT_MAX; 
    int greater = 0; 


    int main_small = 0; 
    int main_middle_1 = 0; 

    int main_main_small = 0; 

    for(int i = 0; i<n; i++) 
    { 
    if(a[i] <= small) 
     small = a[i]; 

    else if(a[i] <= middle_1) 
    { 
     middle_1 = a[i]; 
     main_small = small; 
    } 

    else if(a[i] <= middle_2) 
    { 
     middle_2 = a[i]; 
     main_middle_1 = middle_1; 
     main_main_small = main_small; 
    } 
    else 
    { 
     greater = a[i]; 
     break; 
    } 
    } 
    //end of loop 

    if(greater!=0) 
    { 
     cout<<"\n"<<main_main_small<<"\t"<<main_middle_1<<"\t"  <<middle_2<<"\t"<<greater<<"\n"; 

    } 
    else 
     cout<<"\n No such Quadruple"; 
    return 1; 
} 

int main() 
{ 
    int arr[20] = {6,7,5,1,4,3,0,7,2,11}; 
    int n = 10; 

    sortedSubseqFour(arr,n); 
    return 0; 
} 

Cách tiếp cận trên ghi nhớ tất cả các lớp tối thiểu khi đặt mức tối thiểu hiện tại. Mã tương tự cũng có thể được sử dụng cho một chuỗi được sắp xếp có kích thước 3 trong một mảng bằng cách loại bỏ phần 'main_main_small' và middle_2 của mã.

Nếu, cùng một mã được mở rộng tối đa kích thước 'k' thì tối thiểu là i, chúng ta phải nhớ tất cả các giá trị tối thiểu trước i, (tức là min_1, min_2, ... cho đến min_i. Chỉ ở mức tối thiểu cuối cùng, (nghĩa là, giá trị lớn nhất trong chuỗi tiếp theo của chúng ta, chúng ta chỉ phá vỡ và không cần phải nhớ đến mức tối thiểu trước đó hoặc hiện tại.

Vui lòng thông báo nếu có lỗi nào được phát hiện!

Answer 4

Bạn có thể tìm thấy chuỗi tăng dài nhất và xem kích thước của nó nếu lớn hơn 4 (hoặc thậm chí k trong trường hợp bạn cần tìm nó cho một câu hỏi tổng quát hơn). Nếu độ dài của hậu quả tăng dài nhất nhỏ hơn 4 (hoặc k), bạn có thể báo cáo rằng không tồn tại các chuỗi đó. LIS có thể được phát hiện ra trong O(nlog(n))

Answer 5

Đối với mỗi phần tử, tìm chỉ số phần tử tiếp theo lớn hơn khác -1 Bây giờ nghĩ về điều này như một đồ thị và tìm thấy một con đường có chiều dài k (nếu nó tồn tại) Điều này có thể được thực hiện dễ dàng trong thời gian tuyến tính bằng cách sử dụng hashtable và memoization.