# Share my 4 kinds of java solution{"5 lines 8 ms", "12 lines 6 ms", "9 lines 4 ms", "10 lines 4ms"}

• ``````public class Solution {
//#method 1: 5 lines 8 ms O(log(m+n)+m+n)
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int[] nums3 = new int[nums1.length + nums2.length];
System.arraycopy(nums1, 0, nums3, 0, nums1.length);
System.arraycopy(nums2, 0, nums3, nums1.length, nums2.length);
Arrays.sort(nums3);
return (nums3[nums3.length >> 1] + nums3[(nums3.length - 1) >> 1]) / 2.0;
}

// #method 2: 12 lines 6 ms O(m+n)
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int[] nums3 = new int[nums1.length + nums2.length];
for(int i = 0, j = 0, k = 0; i < nums1.length || j < nums2.length; ++k) {
if(i == nums1.length) {
nums3[k] = nums2[j++];
} else if(j == nums2.length) {
nums3[k] = nums1[i++];
} else if(nums1[i] <= nums2[j]) {
nums3[k] = nums1[i++];
} else {
nums3[k] = nums2[j++];
}
}
return (nums3[nums3.length >> 1] + nums3[(nums3.length - 1) >> 1]) / 2.0;
}

// #method 3: 15 lines 4 ms O(m+n)
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int nums1Mid = nums1.length - 1, nums2Mid = nums2.length - 1;
while(true) {
int L1 = nums1Mid == -1 ? Integer.MIN_VALUE : nums1[nums1Mid >> 1];
int R1 = nums1Mid == (2 * nums1.length - 1) ? Integer.MAX_VALUE : nums1[(nums1Mid + 1) >> 1];
int L2 = nums2Mid == -1 ? Integer.MIN_VALUE : nums2[nums2Mid >> 1];
int R2 = nums2Mid == (2 * nums2.length - 1) ? Integer.MAX_VALUE : nums2[(nums2Mid + 1) >> 1];
if(L1 > R2) {
nums1Mid--;
nums2Mid++;
} else if(L2 > R1) {
nums2Mid--;
nums1Mid++;
} else {
return (Math.max(L1, L2) + Math.min(R1, R2)) / 2.0;
}
}
}

// #method 3(shorter): 9 lines 4 ms O(m+n)
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int offset = 0;
while(true) {
int L1 = (nums1.length - 1 - offset) == -1 ? Integer.MIN_VALUE : nums1[(nums1.length - 1 - offset) >> 1];
int R1 = (nums1.length - 1 - offset) == (2 * nums1.length - 1) ? Integer.MAX_VALUE : nums1[((nums1.length - 1 - offset) + 1) >> 1];
int L2 = (nums2.length - 1 + offset) == -1 ? Integer.MIN_VALUE : nums2[(nums2.length - 1 + offset) >> 1];
int R2 = (nums2.length - 1 + offset) == (2 * nums2.length - 1) ? Integer.MAX_VALUE : nums2[((nums2.length - 1 + offset) + 1) >> 1];
if(L1 > R2) offset++;
else if(L2 > R1) offset--;
else return (Math.max(L1, L2) + Math.min(R1, R2)) / 2.0;
}
}

// #method 4: 12 lines 4 ms O(log(m+n))
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if(nums1.length < nums2.length) return findMedianSortedArrays(nums2, nums1);
int low = -1, high = 2 * nums2.length + 1;
while(true) {
int mid2 = (low + high) / 2;
int mid1 = nums1.length + nums2.length - mid2;  // ==nums1.length - nums2.length + 2 * nums2.length - mid2;
int L1 = mid1 == 0 ? Integer.MIN_VALUE : nums1[(mid1 - 1) / 2];
int R1 = mid1 == (2 * nums1.length) ? Integer.MAX_VALUE : nums1[mid1 / 2];
int L2 = mid2 == 0 ? Integer.MIN_VALUE : nums2[(mid2 - 1) / 2];
int R2 = mid2 == (2 * nums2.length) ? Integer.MAX_VALUE : nums2[mid2 / 2];
if(L1 > R2) low = (low + high) / 2;
else if(L2 > R1) high = (low + high) / 2;
else return (Math.max(L1, L2) + Math.min(R1, R2)) / 2.0;
}
}

// #method 4(shorter): 10 lines 4 ms O(log(m+n))
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if(nums1.length < nums2.length) return findMedianSortedArrays(nums2, nums1);
int low = -1, high = 2 * nums2.length + 1, start = nums1.length - nums2.length;
while(true) {
int L1 = (start + (low + high) / 2) == 0 ? Integer.MIN_VALUE : nums1[((start + (low + high) / 2) - 1) / 2];
int R1 = (start + (low + high) / 2) == (2 * nums1.length) ? Integer.MAX_VALUE : nums1[(start + (low + high) / 2) / 2];
int L2 = (2 * nums2.length - (low + high) / 2) == 0 ? Integer.MIN_VALUE : nums2[((2 * nums2.length - (low + high) / 2) - 1) / 2];
int R2 = (2 * nums2.length - (low + high) / 2) == (2 * nums2.length) ? Integer.MAX_VALUE : nums2[(2 * nums2.length - (low + high) / 2) / 2];
if(L1 > R2) high = (low + high) / 2;
else if(L2 > R1) low = (low + high) / 2;
else return (Math.max(L1, L2) + Math.min(R1, R2)) / 2.0;
}
}
}``````

• There is no `O(log(m+n)+m+n)` in the world. It should be `O(m+n)`

• I guess the 1st method is O((m+n)log(m+n))? It uses sort.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.