Giá trị thấp nhất trong phạm vi

Question

Tôi muốn tìm giá trị thấp nhất trong một số phạm vi.
Tôi có phải lặp lại mảng mỗi lần hoặc có phương pháp động nào không?

phép nói rằng tôi có mảng đầu vào:

index: 0 1 2 3 4 5 6 7 
value: 1 4 6 1 6 7 2 3 

và sau đó tôi phải chọn nhỏ nhất trong phạm vi < a, b> (bao gồm). Ví dụ:

min(0,7) = 1 
min(0,2) = 1 
min(4,6) = 2 
min(1,2) = 4 

Tôi quan tâm đến giải pháp nhanh nhất, tốt nhất nên lấy kết quả trong thời gian không đổi.

Mảng sẽ không bị thay đổi trong thời gian chờ đợi.

Answer 1

Nếu bạn định thực hiện nhiều truy vấn trên cùng một tập hợp các số thì bạn sẽ muốn tạo một Cartesian Tree.

Cây Descartes có thể được sử dụng như một phần của cấu trúc dữ liệu hiệu quả cho các truy vấn tối thiểu, phạm vi tìm kiếm yêu cầu giá trị tối thiểu trong chuỗi tiếp giáp của chuỗi gốc.

Như bài viết cho biết, các truy vấn có thể được thực hiện trong thời gian không đổi.

Answer 2

Đây là một nhiệm vụ tiêu chuẩn. Bạn có thể sử dụng chức năng thư viện std. Nó phải là nhanh nhất có thể. Ví dụ từ here:

#include <iostream>  // std::cout 
#include <algorithm> // std::min_element, std::max_element 

int main() { 
    int myints[] = {3,7,2,5,6,4,9}; 

    std::cout << "The smallest element is " << *std::min_element(myints,myints+7) << '\n'; 

    return 0; 
} 

---

T.B. Bạn không thể nhận được kết quả trong thời gian không đổi, vì nếu bạn cần tối thiểu giữa các phần tử N, bạn cần kiểm tra từng phần tử. Độ phức tạp của tác vụ tối thiểu là O (N).

Answer 3

Bạn có thể thử (một cái gì đó không chắc chắn nếu tôi đang thiếu) sau

Nếu bạn được phép một số tiền xử lý, sau đó bạn có thể có một loạt các cực tiểu địa phương (thung lũng).

Mảng này phải được sắp xếp theo các chỉ mục tương ứng.

Khi bạn nhận được khoảng thời gian, hãy thực hiện tìm kiếm nhị phân của chỉ mục dưới trong mảng minima. Chọn cái lớn hơn trong mảng đó. nói I1

Sau đó, thực hiện tìm kiếm nhị phân của chỉ mục đã cho cao hơn trong mảng minima. Chọn cái nhỏ hơn trong mảng đó. nói I2

Nếu I2> = I1, thì ít nhất một địa phương tối thiểu tồn tại trong khoảng thời gian. Chỉ cần so sánh các giá trị tại minima trong khoảng thời gian đó và tại ranh giới để nhận câu trả lời.

Khác, không tồn tại tối thiểu địa phương trong khoảng thời gian. Trong trường hợp này, giá trị tối thiểu phải nằm ở ranh giới của khoảng thời gian. Chỉ cần so sánh hai giá trị và nhận giá trị thấp hơn.

Answer 4

Bạn có thể sử dụng segment tree cho câu hỏi này. This là một trong những hướng dẫn tốt nhất về phân đoạn truy vấn tối thiểu cây và phạm vi.

Tôi đang thực hiện JAVA và mã tự giải thích, vui lòng cho tôi biết nếu bạn có bất kỳ nghi ngờ nào.

public class SegmentTree { 

    private int[] array; 
    private int length; 

    public static SegmentTree initialize(int[] a) { 
     return new SegmentTree(a); 
    } 

    private SegmentTree(int[] a) { 
     length = a.length - 1; 
     int l = (int) (Math.log(a.length)/Math.log(2)); 
     l = (int) (Math.pow(2, l + 1) * 2 - 1); 
     array = new int[l]; 
     initialize(a, 0, a.length - 1, 0); 
    } 

    private int initialize(int[] a, int p, int r, int index) { 
     if (p == r) { 
      array[index] = a[p]; 
      return a[p]; 
     } 
     int q = p + (r - p)/2; 
     array[index] = Math.min(initialize(a, p, q, 2 * index + 1), initialize(a, q + 1, r, 2 * index + 2)); 
     return array[index]; 
    } 

    public int findMin(int p, int r) { 
     return _findMin(p, r, 0, length, 0); 
    } 

    private int _findMin(int qs, int qe, int ss, int se, int i) { 
     if (qs <= ss && se <= qe) { 
      return array[i]; 
     } 
     if (qs > se || qe < ss) { 
      return Integer.MAX_VALUE; 
     } 
     int q = ss + (se - ss)/2; 
     return Math.min(_findMin(qs, qe, ss, q, 2 * i + 1), _findMin(qs, qe, q + 1, se, 2 * i + 2)); 
    } 

    private void print() { 
     int index = 0; 
     for (int k : array) { 
      System.out.println(index + ":" + k); 
      index++; 
     } 
    } 

    public static void main(String[] args) { 
     int[] a = {1, 34, 5, 6, 78, 5, 67, 89}; 
     SegmentTree s = initialize(a); 
     System.out.println(s.findMin(2, 4)); 
    } 
}