Phần tử lớn nhất hiện diện ở phía bên phải của mỗi phần tử trong một mảng

Question

Tôi đã nhận được một mảng (gồm n phần tử) và tôi phải tìm phần tử nhỏ nhất ở bên phải của mỗi phần tử lớn hơn chính nó (phần tử hiện tại).

For example : 
    Array =  {8,20,9,6,15,31} 
Output Array = {9,31,15,15,31,-1} 

Có thể giải quyết vấn đề này trong O(n).? Tôi nghĩ rằng đi qua mảng từ phía bên phải (bắt đầu từ n-2) và xây dựng cây tìm kiếm nhị phân cân bằng cho các phần tử còn lại, như tìm kiếm trong phần tử đó ngay lập tức lớn hơn phần tử hiện tại sẽ là O (logn).

Do đó thời gian phức tạp sẽ đến ra là O (n * (log (n)).

Có một cách tiếp cận tốt hơn cho vấn đề này?

Answer 1

Vấn đề bạn trình bày là không thể giải quyết trong O(n) thời gian, vì bạn có thể giảm sắp xếp để nó và do đó đạt được sắp xếp trong O(n) thời gian. Giả sử có tồn tại một thuật toán mà giải quyết vấn đề trong O(n). Let there be một yếu tố một.

Các thuật toán cũng có thể được sử dụng để tìm các yếu tố nhỏ đến trái và lớn hơn một (bởi đảo ngược mảng trước khi chạy thuật toán). Nó cũng có thể được sử dụng để tìm ra nguyên tố lớn nhất đến đúng (hoặc trái) và nhỏ hơn một (bởi phủ nhận yếu tố trước khi chạy thuật toán).

Vì vậy, sau khi chạy thuật toán bốn lần (trong thời gian tuyến tính), bạn biết phần tử nào nằm ở bên phải và bên trái của mỗi phần tử. Để xây dựng mảng được sắp xếp theo thời gian tuyến tính, bạn cần giữ các chỉ mục của các phần tử thay vì các giá trị. Trước tiên, bạn tìm thấy phần tử nhỏ nhất bằng cách theo dõi "các con trỏ lớn hơn" của bạn trong thời gian tuyến tính, và sau đó thực hiện một đường truyền khác theo hướng khác để thực sự tạo mảng.

Answer 2

Điều này không thể thực hiện được trong O(n), vì chúng tôi có thể giảm Element Distinctness Problem (được biết là có thể thay đổi được trong Omega (nlogn) khi so sánh).

Đầu tiên, chúng ta hãy làm một mở rộng chút cho vấn đề, điều đó không ảnh hưởng đến độ cứng của nó:

Tôi đã được cấp một mảng (n phần tử) và tôi phải tìm phần tử nhỏ nhất trên phía bên phải của mỗi phần tử lớn hơn/bằng so với chính nó (phần tử hiện tại).

Việc bổ sung là chúng ta cho phép các phần tử có giá trị nhỏ hơn (và bên phải), và không chỉ nghiêm chỉnh lớn hơn .

Bây giờ, Cho một ví dụ về sự khác biệt của phần tử arr, hãy chạy thuật toán cho sự cố này và xem có bất kỳ phần tử nào không. ".

Tuy nhiên, vì tính khác biệt của phần tử là Omega(nlogn) so sánh dựa trên, nó cũng gây ra sự cố này.

---

(1) Một biện minh do khiến thêm bình đẳng không làm cho vấn đề khó khăn hơn là - giả định các yếu tố là các số nguyên, chúng tôi chỉ có thể thêm i/(n+1) để mỗi phần tử trong mảng, bây giờ cho mỗi hai yếu tố nếu arr[i] < arr[j] , cũng là arr[i] + i/(n+1) < arr[j] + j/(n+1), nhưng nếu arr[i] = arr[j], thì nếu i<jarr[i] + i/(n+1) < arr[j] + j/(n+1) và chúng tôi cũng có cùng một thuật toán giải quyết vấn đề về mức độ cân bằng.

Answer 3

Những người khác đã chứng minh rằng không thể nói chung để giải quyết trong O (n).

Tuy nhiên, có thể thực hiện trong O (m) trong đó m là kích thước của phần tử lớn nhất của bạn. Điều này có nghĩa là trong một số trường hợp nhất định (ví dụ: nếu mảng đầu vào của bạn được biết là hoán vị của các số nguyên từ 1 đến n) thì có thể thực hiện trong O (n).

Mã bên dưới cho thấy cách tiếp cận, được xây dựng dựa trên phương pháp chuẩn để tính toán phần tử lớn hơn tiếp theo. (Có giải thích tốt về phương pháp này on geeks for geeks)

def next_greater_element(A): 
    """Return an array of indices to the next strictly greater element, -1 if none exists""" 
    i=0 
    NGE=[-1]*len(A) 
    stack=[] 
    while i<len(A)-1: 
     stack.append(i) 
     while stack and A[stack[-1]]<A[i+1]: 
      x=stack.pop() 
      NGE[x]=i+1 
     i+=1 
    return NGE 

def smallest_greater_element(A): 
    """Return an array of smallest element on right side of each element""" 
    top = max(A) + 1 
    M = [-1] * top # M will contain the index of each element sorted by rank 
    for i,a in enumerate(A): 
     M[a] = i 
    N = next_greater_element(M) # N contains an index to the next element with higher value (-1 if none) 
    return [N[a] for a in A] 


A=[8,20,9,6,15,31] 
print smallest_greater_element(A) 

Ý tưởng là tìm phần tử tiếp theo theo thứ tự kích thước với chỉ mục lớn hơn. Yếu tố tiếp theo này sẽ là phần tử nhỏ nhất xuất hiện ở bên phải.