Java에서 두 개의 정렬된 배열의 중앙값 찾기

JAVA 튜토리얼
자바 파일

소개

두 개의 정렬된 배열의 중앙값을 찾는 문제는 전형적인 코딩 인터뷰 질문입니다. 문제는 O(log(min(m, n)))의 시간 복잡도로 중앙값을 효율적으로 찾는 것입니다. 여기서 m과 n은 두 배열의 크기입니다. 이 기사에서는 이러한 효율성을 달성하기 위해 이진 검색을 사용하는 Java 솔루션을 살펴보겠습니다.

문제 설명

두 개의 정렬된 배열 nums1과 nums2가 주어지면 두 개의 정렬된 배열의 중앙값을 찾습니다. 전체 런타임 복잡도는 O(log(min(m, n)))이어야 합니다. 여기서 m과 n은 두 배열의 크기입니다.

접근하다

이 문제를 해결하기 위해 우리는 두 배열 중 더 작은 배열에 대해 이진 검색 접근 방식을 사용합니다. 목표는 왼쪽 절반에 오른쪽 절반의 요소보다 작거나 같은 모든 요소가 포함되도록 두 배열을 분할하는 것입니다. 단계별 설명은 다음과 같습니다.

1. nums1이 더 작은 배열인지 확인하세요: 더 쉬운 이진 검색을 위해 nums1이 더 작은 배열인지 확인하세요.
2. 이진 검색 수행: nums1에서 이진 검색을 사용하여 올바른 파티션을 찾습니다.
3. 분할: 왼쪽에는 낮은 요소가 포함되고 오른쪽에는 높은 요소가 포함되도록 두 배열을 분할합니다.
4. 중앙값 계산: 파티션을 기준으로 중앙값을 계산합니다.

해결책

다음은 솔루션의 자세한 Java 구현입니다.

public class MedianOfTwoSortedArrays {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // Ensure nums1 is the smaller array
        if (nums1.length > nums2.length) {
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }

        int x = nums1.length;
        int y = nums2.length;
        int low = 0, high = x;

        while (low <= high) {
            int partitionX = (low + high) / 2;
            int partitionY = (x + y + 1) / 2 - partitionX;

            // Edge cases
            int maxX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];
            int minX = (partitionX == x) ? Integer.MAX_VALUE : nums1[partitionX];
            int maxY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];
            int minY = (partitionY == y) ? Integer.MAX_VALUE : nums2[partitionY];

            if (maxX <= minY && maxY <= minX) {
                // Correct partition
                if ((x + y) % 2 == 0) {
                    return (Math.max(maxX, maxY) + Math.min(minX, minY)) / 2.0;
                } else {
                    return Math.max(maxX, maxY);
                }
            } else if (maxX > minY) {
                high = partitionX - 1;
            } else {
                low = partitionX + 1;
            }
        }

        throw new IllegalArgumentException("Input arrays are not sorted");
    }

    public static void main(String[] args) {
        MedianOfTwoSortedArrays solution = new MedianOfTwoSortedArrays();

        int[] nums1 = {1, 3};
        int[] nums2 = {2};
        System.out.println("Median: " + solution.findMedianSortedArrays(nums1, nums2)); // Output: 2.0

        int[] nums1_2 = {1, 2};
        int[] nums2_2 = {3, 4};
        System.out.println("Median: " + solution.findMedianSortedArrays(nums1_2, nums2_2)); // Output: 2.5
    }
}

설명

1. 초기화: nums1이 더 작은 배열인지 확인하세요.
2. 이진 검색: nums1에서 이진 검색을 수행하여 올바른 파티션을 찾습니다.
3. 파티션 및 중앙값 계산: 왼쪽 요소의 최대값과 오른쪽 요소의 최소값을 계산하여 중앙값을 찾습니다.

결론

이 이진 검색 접근 방식은 두 개의 정렬된 배열의 중앙값을 찾는 효율적인 솔루션을 제공합니다. 이 솔루션은 더 작은 배열에서 이진 검색을 활용하여 O(log(min(m, n)))의 시간 복잡도를 달성하므로 대규모 입력 배열에 적합합니다.

위 내용은 Java에서 두 개의 정렬된 배열의 중앙값 찾기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!