Commit860cfb3

authored

Merge pull requestneetcode-gh#1271 from MHamiid/patch-2

Add 4-Median-of-Two-Sorted-Arrays.c

2 parentsdaf98b0 +97e712c commit860cfb3Copy full SHA for 860cfb3

File tree

+62

-0

lines changed

+62

-0

lines changed

Lines changed: 62 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,62 @@`
	`1`	`+/*`
	`2`	`+ Time: log(min(n, m))`
	`3`	`+ Space: O(1)`
	`4`	`+*/`
	`5`	`+`
	`6`	`+#definemin(x,y) ((x < y) ? (x) : (y))`
	`7`	`+#definemax(x,y) ((x > y) ? (x) : (y))`
	`8`	`+`
	`9`	`+doublefindMedianSortedArrays(intnums1,intnums1Size,intnums2,intnums2Size){`
	`10`	`+int*A=nums1;`
	`11`	`+int*B=nums2;`
	`12`	`+intASize=nums1Size;`
	`13`	`+intBSize=nums2Size;`
	`14`	`+`
	`15`	`+inttotal=nums1Size+nums2Size;`
	`16`	`+inthalf=total /2;`
	`17`	`+`
	`18`	`+if(nums2Size<nums1Size)`
	`19`	`+ {`
	`20`	`+A=nums2;`
	`21`	`+B=nums1;`
	`22`	`+ASize=nums2Size;`
	`23`	`+BSize=nums1Size;`
	`24`	`+ }`
	`25`	`+`
	`26`	`+intl=0;`
	`27`	`+intr=ASize-1;`
	`28`	`+`
	`29`	`+while(true)`
	`30`	`+ {`
	`31`	`+inti=l+ ((r-l-2+1) /2);// A Mid, round down instead of rounding towards 0`
	`32`	`+intj=half-i-2;// B Mid`
	`33`	`+`
	`34`	`+`
	`35`	`+intAleft=i >=0 ?A[i] :INT_MIN;`
	`36`	`+intAright= (i+1)<ASize ?A[i+1] :INT_MAX;`
	`37`	`+intBleft=j >=0 ?B[j] :INT_MIN;`
	`38`	`+intBright= (j+1)<BSize ?B[j+1] :INT_MAX;`
	`39`	`+`
	`40`	`+// partition is correct`
	`41`	`+if(Aleft <=Bright&&Bleft <=Aright)`
	`42`	`+ {`
	`43`	`+// Odd`
	`44`	`+if(total %2)`
	`45`	`+ {`
	`46`	`+returnmin(Aright,Bright);`
	`47`	`+ }`
	`48`	`+`
	`49`	`+// Even`
	`50`	`+return (max(Aleft,Bleft)+min(Aright,Bright)) /2.0;`
	`51`	`+ }`
	`52`	`+elseif(Aleft>Bright)`
	`53`	`+ {`
	`54`	`+r=i-1;`
	`55`	`+ }`
	`56`	`+else`
	`57`	`+ {`
	`58`	`+l=i+1;`
	`59`	`+ }`
	`60`	`+ }`
	`61`	`+`
	`62`	`+}`

Comments

(0)