범위에서 가장 낮은 값

Question

일부 범위에서 가장 낮은 값을 찾고 싶습니다.
매번 배열을 반복해야합니까 아니면 동적 방법이 있습니까?

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

다음 I 범위 < A, B> (포함)의 최소를 선택해야한다 :

는 I 입력 어레이가 있다고하자. 예 :

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

가장 빠른 솔루션에 관심이 있으신 분은 일정 시간 내에 결과를 얻는 것이 가장 좋습니다.

배열은 그동안 변경되지 않습니다.

Answer 1

동일한 숫자 집합에 대해 여러 개의 쿼리를 수행하려는 경우 Cartesian Tree을 구성해야합니다.

데카르트 트리는 범위 최소값 쿼리, 즉 원래 시퀀스의 인접한 하위 시퀀스에서 최소값을 요청하는 쿼리와 관련된 범위 검색 문제의 효율적인 데이터 구조의 일부로 사용될 수 있습니다.

기사에 따르면 쿼리는 일정 시간 내에 수행 될 수 있습니다.

Answer 2

이것은 표준 작업입니다. std 라이브러리 기능을 사용할 수 있습니다. 가능한 가장 빠른 것이어야합니다. 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; 
} 

---

P.S. N 개의 요소 사이에 최소값이 필요한 경우 각 요소를 검사해야하기 때문에 일정한 시간에 결과를 얻을 수 없습니다. 최소 작업 복잡성은 O (N)입니다.

Answer 3

다음과 같은 (확실하지 내가 놓친 경우 뭔가를) 시도 할 수 있습니다 당신은 몇 가지 전처리를 허용하는 경우

, 당신은 지역의 최소값 (계곡)의 배열을 가질 수 있습니다.

이 배열은 각 색인에 따라 정렬되어야합니다.

간격을 얻은 후에는 최소 배열에서 낮은 색인의 2 진 검색을 수행하십시오. 해당 배열에서 더 큰 것을 선택하십시오. I1을 말하십시오

그런 다음 최소 배열에서 더 높은 주어진 색인의 2 진 검색을 수행하십시오. 해당 배열에서 더 작은 것을 선택하십시오. I2를 말하자면

I2> = I1이면 적어도 하나의 지역 최소값이 그 간격에 존재한다. 해당 간격의 최소값에서 값을 비교하고 경계에서의 값을 비교하면됩니다.

그렇지 않으면 간격에 로컬 최소값이 없습니다. 이 경우 최소값은 간격의 경계에 있어야한다. 두 값을 비교하여 더 낮은 값을 얻으십시오.

Answer 4

이 질문에 segment tree을 사용할 수 있습니다. This은 세그먼트 트리 및 범위 최소 쿼리에 대한 최고의 자습서 중 하나입니다.

JAVA 구현을 제공하고 있으며 코드는 자명하다. 의문 사항이 있으면 알려 주시기 바랍니다.

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)); 
    } 
}