[2011 년 408 진 제] 선형 표.

[문제 설명] 길이 가 L (L ≥ 1) 인 오름차 서열 S 로 [L / 2] 번 째 위치 에 있 는 수 를 S 의 중위 라 고 한다.
예 를 들 어 서열 S1 = (11, 13, 15, 17, 19) 이면 S1 의 중위 수 는 15 이다.
두 서열 의 중위 수 는 그들의 모든 요 소 를 포함 하 는 오름차 서열 의 중위 수 이다.
예 를 들 어 S2 = (2, 4, 6, 8, 20) 이면 S1 과 S2 의 중위 수 는 11 이다.
기 존의 두 개의 등장 오름차 서열 A 와 B 는 시간 과 공간 두 가지 측면 에서 가능 한 한 효율 적 인 알고리즘 을 설계 하여 두 서열 A 와 B 의 중위 수 를 찾 아 냈 다.
【 테스트 샘플 】 S1 = {11, 13, 15, 17, 19} S2 = {2, 4, 6, 8, 20} [출력 결과] 11
알고리즘 사고
각각 두 개의 오름차 서열 A, B 의 중위 수 를 구하 고 a 와 b 로 설정한다.
4. 567917. 만약 a = b 라면 a 또는 b 는 원 하 는 중위 수 이 고 알고리즘 이 끝 납 니 다
약 a
4. 567918. 4. 567917. 만약 에 a > b 가 B 에서 작은 사람 이 있 는 서열 의 절반 을 버 리 는 동시에 A 가 있 는 서열 의 절반 을 버 리 고 두 번 버 리 는 요소 의 개수 가 같 아야 한다
보 존 된 두 개의 오름차 서열 에서 상기 과정 을 반복 하고 두 서열 에 모두 하나의 요소 만 포함 할 때 까지 작은 자 는 원 하 는 중위 수 이다.
구체 적 인 설명:
만약 에 a 도 왼쪽 에 있 고 중심 점 이 아니 라 중위수 와 모순 된다.동 리 는 B 의 오른쪽 에 있 지 않다.만약 a > b 시 원 리 는 같다.A 길이 가 홀수 일 때 왼쪽 = 오른쪽, 바로 버 리 면 됩 니 다. A 길이 가 짝수 일 때 왼쪽 + 1 = 오른쪽.만약 a 가 처음부터 끝까지 A 를 유지한다 면, B 는 항 수 를 비교 하면, 즉 길이 가 같다.
상기 알고리즘 의 시간 복잡 도 는 O (log2n) 이 고 공간 복잡 도 는 O (n) 이다.

//            
int middle_search(int A[],int B[],int n)
{
    int m1,m2,s1,s2,d1,d2;
    s1=s2=0;
    d1=d2=n-1;
    while(s1!=d1||s2!=d2)
    {
        m1=(s1+d1)/2;
        m2=(s2+d2)/2;
        if(A[m1]==B[m2])
            return A[m1];
        if(A[m1]

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[문제 설명] 길이 가 L (L ≥ 1) 인 오름차 서열 S 로 [L / 2] 번 째 위치 에 있 는 수 를 S 의 중위 라 고 한다. 예 를 들 어 서열 S1 = (11, 13, 15, 17, 19) 이면 S1 의...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

[2011 년 408 진 제] 선형 표.

좋은 웹페이지 즐겨찾기