Câu hỏi Trong mảng chưa được sắp xếp, hãy thay thế mọi phần tử bằng phần tử lớn hơn đầu tiên sang phải


Trong một mảng chưa được phân loại, chúng ta phải thay thế mọi phần tử bằng phần tử đầu tiên sang phải lớn hơn phần tử hiện tại. Nếu không có phần tử nào ở bên phải lớn hơn thì nó sẽ được thay thế bằng -1.

Thí dụ:

3  1  2  5  9  4  8   should be converted to
5  2  5  9 -1  8 -1

Tôi có thể nghĩ về giải pháp tầm thường, nơi chúng tôi kiểm tra mọi phần tử với toàn bộ mảng Ο (n²) dung dịch. Có cách nào tốt hơn để làm điều này?


11
2018-03-06 18:33


gốc


không phải là -1 2 5 9 -1 8 -1? - lakesh
@ lakesh: Theo như tôi hiểu, 5 là giá trị đầu tiên lớn hơn 3 đó là bên phải của vị trí đầu tiên - Niklas B.
@NiklasB. oh ok.được hiểu sai câu hỏi. - lakesh
Lưu ý rằng thuật toán tầm thường chỉ O(n^2) trong trường hợp xấu nhất. Nó phải là O(n) Trung bình. - nwellnhof
@nwellnhof: Thật sao? Làm như thế nào? Nó không rõ ràng với tôi - Niklas B.


Các câu trả lời:


Ý tưởng chính là xử lý mảng theo thứ tự ngược lại (từ phải sang trái). Chúng tôi thực hiện một vài quan sát:

  • Nếu chúng tôi hiện đang xử lý chỉ mục tôi, k> j> tôi và A[k] ≤ A[j], sau đó chúng tôi gọi yếu tố k không liên quan, bởi vì nó sẽ không bao giờ là kết quả của bất kỳ phần tử nào 1, 2, ..., k
  • Các yếu tố liên quan bên phải của chỉ mục tôi do đó tạo thành một chuỗi tăng dần đơn điệu A[i+1..n-1].

Trong ví dụ của bạn, chuỗi các phần tử liên quan sẽ từ phải sang trái:

       []    
      [8]
    [4,8]
      [9]
    [5,9]
  [2,5,9]
  [1,5,9]

Nó trông giống như một chồng, và chúng tôi thực sự có thể sử dụng một ngăn xếp để duy trì chuỗi này giữa các lần lặp.

Khi xử lý một phần tử mới, trước tiên chúng ta cần tìm kết quả cho phần tử mảng. Quan sát là kết quả là phần tử trên cùng của ngăn xếp không phải bị vô hiệu bởi phần tử mới. Vì vậy, chúng ta chỉ có thể bật từ ngăn xếp tất cả các phần tử đã trở nên không liên quan. Vậy thì trên đầu trang là kết quả của chúng tôi. Sau đó chúng ta có thể đẩy phần tử mới bởi vì nó có liên quan theo định nghĩa của chúng ta.

stack = []
A = [3, 1, 2, 5, 9, 4, 8]
result = [-1]*len(A)
for i := len(A) - 1 to 0:
    # remove all elements made irrelevant by A[i]
    while not stack.empty() && stack.top() <= A[i]:
        stack.pop()
    # now the top of the stack is the result for index i
    if not stack.empty():
        R[i] = stack.top()
    # push the new element on the stack. The stack will still contain all relevant 
    # elements in increasing order from top to bottom
    stack.push(A[i])

Vòng lặp bất biến cho phép lặp i Là "stack chứa phần tử của các phần tử liên quan ở bên phải của chỉ mục iNó rất dễ dàng để xác minh và ngụ ý tính chính xác của thuật toán này.

Mỗi phần tử được đẩy và xuất hiện nhiều nhất một lần, vì vậy chúng tôi có tổng thời gian chạy Ο (n).


11
2018-03-06 19:47



Tôi nghĩ bạn muốn nói A[k] ≤ A[j]. Ngoài ra, tôi nghĩ rằng mã của bạn sẽ dễ đọc hơn nếu bạn đặt các phần của if và while trên một dòng của riêng mình. Ngoài chi tiết: +1 - Walter Tross
Ai có thể downvoted đưa ra một lý do? N.B .: Tôi không có quan hệ với tác giả của câu trả lời này - Walter Tross
@ WalterTross: Vâng, bạn đã đúng, đã thay đổi điều đó. Tôi cũng đã thêm một số cú pháp tô sáng :) - Niklas B.
Thuật toán chính xác giống như tôi, ngoại trừ từ phải sang trái. bạn có thể đã nói điều này như một bình luận trong bài viết của tôi. Cái này không công bằng. - Trying
@Trying: Trước hết, khái niệm nó khá nhiều một điều khác nhau và một chút dễ dàng hơn để thực hiện. Thứ hai, tôi đã cố gắng để thêm một lời giải thích thực tế và biện minh lý do tại sao điều này hoạt động, cũng như lý do tại sao nó có thời gian chạy dự định. Tôi cảm thấy rằng nó thêm vào mục đích theo nhiều cách. Ngoài ra, bạn không thể xác nhận quyền sở hữu ý tưởng đằng sau điều này, vì nó khá rõ ràng, cũng như nhận xét của người khác - Niklas B.


bạn có thể sử dụng ngăn xếp và độ phức tạp thời gian là O(N).

algo: Bắt đầu từ phía bên trái và di chuyển về phía bên phải. Khi bạn chọn một phần tử tạo thành mảng (cho phép nói x) bật ngăn xếp cho đến khi các phần tử từ ngăn xếp (cho phép nói y) có phần tử lớn hơn phần tử mảng tức là x> y. Hơn đẩy phần tử tức là x lên ngăn xếp.

ví dụ. {40,50,11,32,55,68,75} . đây s là ngăn xếp.

40, như s là trống đẩy nó. s: 40

50, như s.peek () <50 để pop 40 (phần tử lớn hơn 40 là 40) so với đẩy 50. s: 50

Yếu tố cao hơn tiếp theo là 40 - 50.

11, s.peek ()> 11 để đẩy 11. s: 50, 11

32, s.peek () <32, vì vậy hãy bật phần tử và bây giờ nó là 50, lớn hơn 32, do đó nhấn 32. s: 50 ,32

Yếu tố cao hơn tiếp theo là 11 - 32.

55, s.peek () <55, do đó, bật phần tử, tức là 32 hơn pop tiếp theo cũng như 50 <55, so với đẩy 55. s: 55.

Yếu tố cao hơn tiếp theo là 32 - 55.

Yếu tố cao hơn tiếp theo là 50 - 55.

68, s.peek () <68 để bật nó và nhấn 68. s: 68

75, s.peek () <75 để bật nó và nhấn 75 s:75.

Yếu tố cao hơn tiếp theo là 68 - 75.

Vì mảng không có bất kỳ phần tử nào, chỉ cần pop stack nói rằng tất cả các phần tử bên trong mảng không có phần tử lớn hơn, tức là -1.

Yếu tố cao hơn tiếp theo là 75 - -1.

Cùng một bản ngã trong mã:

public static void fun(int[] a) {
    Stack<Integer> s = new Stack<Integer>();
    s.push(a[0]);

    for (int i = 1; i < a.length; i++) {
        if (s.peek() != null) {
            while (true) {
                if (s.peek() == null || s.peek() > a[i]) {
                    break;
                }
                System.out.println(s.pop() + ":" + a[i]);
            }
        }
        s.push(a[i]);
    }
    while (s.peek() != null) {
        System.out.println(s.pop() + ":" + -1);
    }
}

2
2018-03-06 19:19



Bạn làm gì với người không -1 yếu tố? Làm thế nào để bạn tìm thấy giá trị lớn hơn tiếp theo? - Niklas B.
Tôi không nghĩ rằng bạn đã nghĩ rằng điều này là đủ. Bạn có thể cho (thậm chí rất thô) mã giả cho thuật toán này không? - Daniel Harms
Mặc dù tôi nghĩ rằng cách tiếp cận của bạn là chính xác. Nó thực sự có thể hoạt động O(n). Việc triển khai của bạn sai, tuy nhiên - Niklas B.
Mặc dù việc triển khai của bạn có những lỗi nhỏ nhưng thuật toán là chính xác. Ngay sau khi tôi nhìn vào câu hỏi tôi đã suy nghĩ phương pháp của Niklas B, không nghĩ rằng vòng lặp từ trái sang phải sẽ làm việc quá! - Leo
Đã không downvote, nhưng tôi đoán đó là vì ví dụ Java của bạn không hoạt động - Niklas B.