In this Leetcode Median of two sorted arrays problem solution we have given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).
Problem solution in Python.
class Solution: # @return a float def findMedianSortedArrays(self, A, B): med1 = med2 = i = j = 0 n = len(A) + len(B) while (i + j) <= n / 2: if i < len(A) and j < len(B): med2 = med1 if A[i] < B[j]: med1 = A[i] i += 1 else: med1 = B[j] j += 1 elif i < len(A): med2 = med1 med1 = A[i] i += 1 elif j < len(B): med2 = med1 med1 = B[j] j += 1 if n % 2 == 0: return (med1 + med2) / 2.0 else: return med1
Problem solution in Java.
class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { ArrayList<Integer> list = new ArrayList<Integer>(); for(int i=0;i<nums1.length;i++) { list.add(nums1[i]); } for(int i=0;i<nums2.length;i++) { list.add(nums2[i]); } Collections.sort(list); int size=list.size(); if (size % 2 == 1) return (double) list.get(size/2); return (double) (list.get((size/2)-1) + list.get(size/2) )/2; } }
Problem solution in C++.
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { nums1.insert(nums1.begin(), nums2.begin(), nums2.end()); sort(nums1.begin(), nums1.end()); int median = nums1.size()/2; if(nums1.size()%2 == 1) { return nums1[median]; } else { return (double)(nums1[median]+nums1[median-1])/2; } }
Problem solution in C.
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){ int len = nums1Size + nums2Size; int merged[len]; int i = 0, j = 0, idx = 0; while (i < nums1Size || j < nums2Size) { if (i < nums1Size && j < nums2Size) { if (nums1[i] < nums2[j]) { merged[idx++] = nums1[i++]; } else { merged[idx++] = nums2[j++]; } } else if (i < nums1Size) { merged[idx++] = nums1[i++]; } else { merged[idx++] = nums2[j++]; } } if (len % 2 == 0) { return ((merged[len/2 - 1] + merged[len/2]) / 2.0); } else { return merged[len/2]; } }
0 Comments