LeetCode 챌린지: 정렬된 배열 병합 - JavaScript 솔루션

인터뷰 150

정렬된 배열을 병합하는 것은 전형적인 문제이며 이를 효율적으로 해결하는 방법을 이해하는 것은 코딩 인터뷰에 필수적입니다. 이 게시물에서는 JavaScript를 사용하여 상위 인터뷰 150개 질문 챌린지의 일부인 LeetCode의 88. Merge Sorted Array를 다루겠습니다. 문제, 그 뉘앙스, 깨끗하고 최적의 솔루션에 대해 자세히 알아보세요!

? 문제 설명
내림차순으로 정렬된 두 개의 정수 배열 nums1과 nums2가 제공됩니다. 당신의 임무는 nums1이 정렬된 상태로 유지되도록 nums2를 nums1로 병합하는 것입니다.

하지만 반전도 있습니다.

nums1에는 nums2의 요소를 수용할 만큼 충분한 공간(0으로 설정)이 있습니다.
최종 병합 결과는 nums1에 저장되어야 합니다.

? 예시

예시 1

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]

예시 2

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]

예시 3

Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]

? 주요 인사이트

• 내부 병합: 추가 공간을 사용하지 않고 nums1을 채워야 합니다. 이는 배열을 직접 수정하는 것을 의미합니다.
• 뒤에서 앞으로 전략: nums1은 끝에 여분의 공간이 있으므로 뒤에서 채우는 것이 가장 효율적인 접근 방식입니다.

? JavaScript 솔루션: 2점 접근 방식

최적의 솔루션은 두 어레이의 끝에서 시작하여 2점 접근 방식을 활용합니다. 이렇게 하면 가장 큰 요소가 먼저 배치되어 불필요한 요소 이동을 방지할 수 있습니다.

var merge = function(nums1, m, nums2, n) {
    // Initialize pointers for nums1, nums2, and the last index of nums1
    let p1 = m - 1;
    let p2 = n - 1;
    let p = m + n - 1;

    // Compare elements from the end and place the largest at the back
    while (p1 >= 0 && p2 >= 0) {
        if (nums1[p1] > nums2[p2]) {
            nums1[p] = nums1[p1];
            p1--;
        } else {
            nums1[p] = nums2[p2];
            p2--;
        }
        p--;
    }

    // Copy remaining elements from nums2 (if any)
    while (p2 >= 0) {
        nums1[p] = nums2[p2];
        p2--;
        p--;
    }
};

? 작동 원리

1. 끝부터 시작:
   nums1과 nums2의 가장 큰 요소를 비교합니다(p1
   사용). 및 p2 포인터).
   끝에 더 큰 요소를 배치하세요. nums1(p 포인터 사용).

2. 감소 포인터:
   요소를 처리하면서 p1, p2, p를 이동하세요.

3. 나머지 요소 처리:
   nums2에 요소가 남아 있으면 해당 요소를 nums1에 복사합니다. (아니
   이미 위치에 있으므로 nums1의 요소를 복사해야 합니다.)

? 복잡성 분석

? 드라이런
입력:
nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3

단계 p1 p2 p nums1
초기화 2 2 5 [1,2,3,0,0,0]
1 2 2 5 [1,2,3,0,0,6]
2 2 1 4 [1,2,3,0,5,6]
3 2 0 3 [1,2,3,3,5,6]
4 1 0 2 [1,2,2,3,5,6]
5 0 0 1 [1,2,2,3,5,6]
최종 출력: [1,2,2,3,5,6]

? 직접 시도해 보세요!

LeetCode에서 전체 문제와 테스트 사례를 확인해보세요. 코드를 보지 않고 솔루션 구현에 도전해보세요!

✨ 인터뷰를 위한 전문가의 조언

1. 제약 조건을 명확히 합니다. 추가 공간을 사용할 수 있는지 또는 장소는 필수입니다.
2. 특정 사례에 대한 최적화: nums2가 비어 있는 경우 고려 또는 nums1에는 초기 요소가 없습니다(m = 0).
3. 논리 살펴보기: 두 포인터 접근 방식 설명 면접관에게 명확하게 전달됩니다.

질문이나 의견이 있으신가요? 아래 댓글에서 공유해 주세요! 함께 배워봅시다. ?

위 내용은 LeetCode 챌린지: 정렬된 배열 병합 - JavaScript 솔루션의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!