두 오름차 순 의 중위 수 를 구하 다.

1. 등장 서열 문 제 는 왕도 대학원 데이터 구조 서 의 길이 가 L (L ≥ 1) 인 오름차 서열 S 에서 유래 한 것 으로 전체 8968 ° L / 2 * 8969 ° 의 위치 에 있 는 수 를 S 의 중위 라 고 한다.예 를 들 어 만약 에 서열 S1 = (11, 13, 15, 17, 19) 이 라면 S1 의 중위 수 는 15 이 고 두 서열 의 중위 수 는 그들의 모든 요 소 를 포함 한 오름차 서열 의 중위 수 이다.예 를 들 어 S2 = (2, 4, 6, 8, 20) 이면 S1 과 S2 의 중위 수 는 11 이다.현재 두 개의 등장 오름차 서열 A 와 B 가 있 는데 시간 과 공간 두 가지 측면 에서 가능 한 한 효율 적 인 알고리즘 을 설계 하여 두 서열 A 와 B 의 중위 수 를 찾 아 보 자.1.1 O (n) 의 해법 은 바로 처음부터 끝까지 모두 len 개 수 를 세 는 것 이다. 이때 두 바늘 이 가리 키 는 숫자 가 작은 사람 이 바로 원 하 는 것 이다.

int midNum ( int* a, int* b, int len ) {
	int i = 0, j = 0, k = 0;

	for ( ; k < len-1; k++ ) {
		if ( a[i] < b[j] ) {
			i++;
		}
		else {
			j++;
		}
	}

	return (a[i] < b[j])? a[i]: b[j];
}

1.2 O (logn) 의 해 는 각각 두 개의 오름차 서열 의 A, B 의 중위 수 a 와 b 를 구한다. ① a = b 라면 두 서열 의 중위 수 를 찾 았 고 a ② a < b 라면 서열 A 의 작은 절반 을 버 리 고 서열 B 의 큰 절반 ③ a > b 를 버 리 면 서열 A 의 큰 절반 을 버린다.시퀀스 B 의 작은 반 반복 과정 을 버 리 고 ① ③ 두 시퀀스 가 모두 하나의 요소 만 포함 할 때 까지 작은 자 에 게 돌아 갑 니 다.

int midNum2 ( int* a, int* b, int n ) {
	int s1 = 0, d1 = n-1, s2 = 0, d2 = n-1;
	int m1, m2;

	while ( s1 != d1 || s2 != d2 ) {
		m1 = ( s1 + d1 ) / 2;
		m2 = ( s2 + d2 ) / 2;

		if ( a[m1] == b[m2] ) {
			return a[m1];
		}
		else if ( a[m1] < b[m2] ) {

			if ( (s1 + d1) % 2 == 0 ) { //        
				s1 = m1; //      
				d2 = m2; //      
			}
			else { //        
				s1 = m1+1; //       
				d2 = m2; //      
			}
		}
		else {
			if ( (s2 + d2) % 2 == 0 ) { //        
				s2 = m2; //      
				d1 = m1; //      
			}
			else { //        
				s2 = m2+1; //       
				d1 = m1; //      
			}
		}

	} // end of while

	return ( a[s1] < b[s2] )? a[s1]: b[s2];
}

2. 비등 장 시퀀스 제목 은 Leetcode 에서 유래:https://leetcode.com/problems/median-of-two-sorted-arrays/ There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
You may assume nums1 and nums2 cannot be both empty.
Example 1:
nums1 = [1, 3] nums2 = [2]
The median is 2.0 Example 2:
nums1 = [1, 2] nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
이 문제 의 해법 을 보 았 다https://leetcode.com/articles/median-of-two-sorted-arrays/
그 는 중위 수의 정의 부터 시작 하여 두 서열 을 i, j 로 나 누 었 다.
left part
right part
A[0], A[1], …, A[i-1]
A[i], A[i+1], …, A[m-1]
B[0], B[1], …, B[j-1]
B[j], B[j+1], …, B[n-1]
그 중 len (left part) = len (right part) max (left part) < min (right part)
실 현 된 코드 는 다음 과 같다.

    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        m = len(nums1)
        n = len(nums2)
        if m > n:
            return self.findMedianSortedArrays(nums2, nums1)

        imin = 0
        imax = m
        halfLen = (m + n + 1) // 2

        while imin <= imax:
            i = (imin + imax) // 2
            j = halfLen - i

            if i < m and nums2[j-1] > nums1[i]:
                # i is too small, should increase it
                imin = i + 1
            elif i > 0 and nums1[i-1] > nums2[j]:
                # i is too big, must decrease it
                imax = i - 1
            else:
                # i is perfect

                if i == 0:
                    maxOfLeft = nums2[j-1]
                elif j == 0:
                    maxOfLeft = nums1[i-1]
                else:
                    maxOfLeft = max(nums1[i-1], nums2[j-1])

                if (m + n) % 2 == 1:
                    return float(maxOfLeft)

                if i == m:
                    minOfRight = nums2[j]
                elif j == n:
                    minOfRight = nums1[i]
                else:
                    minOfRight = min(nums1[i], nums2[j])

                return (maxOfLeft + minOfRight) / 2.0