Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit65cdc7a

Browse files
committed
feat/Find Median of Two Sorted Arrays Without Merging
1 parent78ce39a commit65cdc7a

File tree

2 files changed

+116
-0
lines changed

2 files changed

+116
-0
lines changed
Lines changed: 78 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,78 @@
1+
/**
2+
* Function to find the median of two sorted arrays without merging them.
3+
* This algorithm efficiently uses binary search on the smaller array to achieve O(log(min(n, m))) complexity.
4+
* Sample Problem : https://leetcode.com/problems/median-of-two-sorted-arrays/description/
5+
*
6+
* Approach:
7+
* 1. Ensure nums1 is the smaller array to reduce the number of binary search operations.
8+
* 2. Use binary search to partition both arrays so that elements on the left are less than or equal to elements on the right.
9+
* 3. Based on the combined array length, find the median directly by averaging or picking the middle element.
10+
*
11+
* Time Complexity: O(log(min(n, m))) - where n and m are the lengths of the two arrays.
12+
* Space Complexity: O(1) - only a constant amount of space is used.
13+
*
14+
* Examples:
15+
* nums1 = [1, 3], nums2 = [2]
16+
* The combined array would be [1, 2, 3] and the median is 2.
17+
*
18+
* nums1 = [1, 2], nums2 = [3, 4]
19+
* The combined array would be [1, 2, 3, 4] and the median is (2 + 3) / 2 = 2.5.
20+
*
21+
*@param {number[]} nums1 - First sorted array.
22+
*@param {number[]} nums2 - Second sorted array.
23+
*@returns {number} - The median of the two sorted arrays.
24+
*@throws Will throw an error if the input arrays are not sorted or valid for median calculation.
25+
*/
26+
exportfunctionfindMedianSortedArraysWithoutMerging(nums1,nums2){
27+
// Checks if array are sorted or not
28+
constisSorted=(arr)=>{
29+
for(leti=1;i<arr.length;i++){
30+
if(arr[i]<arr[i-1])returnfalse;
31+
}
32+
returntrue;
33+
};
34+
35+
if(!isSorted(nums1)||!isSorted(nums2)){
36+
thrownewError("Input arrays are not sorted or valid for median calculation.");
37+
}
38+
39+
//First ensure nums1 is the smaller array
40+
if(nums1.length>nums2.length){
41+
[nums1,nums2]=[nums2,nums1];
42+
}
43+
44+
constx=nums1.length;
45+
consty=nums2.length;
46+
letlow=0,high=x;
47+
48+
while(low<=high){
49+
constpartitionX=Math.floor((low+high)/2);
50+
constpartitionY=Math.floor((x+y+1)/2)-partitionX;
51+
52+
// Edge values in case of partitions at boundaries
53+
constmaxX=partitionX===0 ?-Infinity :nums1[partitionX-1];
54+
constminX=partitionX===x ?Infinity :nums1[partitionX];
55+
56+
constmaxY=partitionY===0 ?-Infinity :nums2[partitionY-1];
57+
constminY=partitionY===y ?Infinity :nums2[partitionY];
58+
59+
// Check if partition is correct
60+
if(maxX<=minY&&maxY<=minX){
61+
// Correct partition found, calculate median
62+
constleftMax=Math.max(maxX,maxY);
63+
constrightMin=Math.min(minX,minY);
64+
65+
if((x+y)%2===0){
66+
return(leftMax+rightMin)/2;
67+
}else{
68+
returnleftMax;
69+
}
70+
}elseif(maxX>minY){
71+
// Move towards left in nums1
72+
high=partitionX-1;
73+
}else{
74+
// Move towards right in nums1
75+
low=partitionX+1;
76+
}
77+
}
78+
}
Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
import{findMedianSortedArraysWithoutMerging}from'../findMedianSortedArraysWithoutMerging';
2+
3+
describe('findMedianSortedArrays',()=>{
4+
it('should find the median of two sorted arrays of equal length',()=>{
5+
expect(findMedianSortedArraysWithoutMerging([1,3],[2,4])).toBe(2.5);
6+
expect(findMedianSortedArraysWithoutMerging([1,2],[3,4])).toBe(2.5);
7+
});
8+
9+
it('should find the median when arrays have different lengths',()=>{
10+
expect(findMedianSortedArraysWithoutMerging([1,3],[2])).toBe(2);
11+
expect(findMedianSortedArraysWithoutMerging([1,2,3],[4,5])).toBe(3);
12+
});
13+
14+
it('should find the median when one array is empty',()=>{
15+
expect(findMedianSortedArraysWithoutMerging([],[1])).toBe(1);
16+
expect(findMedianSortedArraysWithoutMerging([],[1,2,3])).toBe(2);
17+
});
18+
19+
it('should handle single element arrays',()=>{
20+
expect(findMedianSortedArraysWithoutMerging([1],[2])).toBe(1.5);
21+
expect(findMedianSortedArraysWithoutMerging([1],[2,3,4])).toBe(2.5);
22+
});
23+
24+
it('should handle arrays with duplicate elements',()=>{
25+
expect(findMedianSortedArraysWithoutMerging([1,2,2],[2,3,4])).toBe(2);
26+
expect(findMedianSortedArraysWithoutMerging([1,1,1],[1,1,1])).toBe(1);
27+
});
28+
29+
it('should throw an error if the arrays are not sorted',()=>{
30+
expect(()=>findMedianSortedArraysWithoutMerging([3,1],[2,4])).toThrow('Input arrays are not sorted or valid for median calculation.');
31+
expect(()=>findMedianSortedArraysWithoutMerging([1,3,5],[4,2])).toThrow('Input arrays are not sorted or valid for median calculation.');
32+
});
33+
34+
it('should work for larger arrays',()=>{
35+
expect(findMedianSortedArraysWithoutMerging([1,2,3,6,8],[4,5,7,9])).toBe(5);
36+
expect(findMedianSortedArraysWithoutMerging([1,5,8,10],[3,7,9,11,12])).toBe(8);
37+
});
38+
});

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp