🚀 go-pugleaf

On Sunday, October 16, 2022 at 12:39:13 PM UTC+2, Ghost wrote:
> W dniu 15.10.2022 o 18:54, Przemek Biernat pisze:
> > On Friday, October 14, 2022 at 9:14:35 PM UTC+2, Ghost wrote: 
> >> W dniu 14.10.2022 o 20:22, Przemek Biernat pisze: 
> >>> 
> >>>>> Może ktoś mam jakąś ofertę dla mnie, 
> >>>>> Dzięki 
> >>>> Na poczatek, zaproponuj rozwiazanie 
> >>>> 
> >>>> https://leetcode.com/problems/median-of-two-sorted-arrays/ 
> >>> 
> >>> Zaproponowałem rozwiązanie. Być może da się to napisać aby działało wydajniej. 
> >> Niby gdzie je zaproponowales? 
> > Przepraszam przypuszczałem że jak dam submit na portalu to zobaczysz mój kod. O to moje rozwiązanie które dostało Accepted. Złożoność to (m+n)/2. Nie udało mi się osiągnąć złożoności log(n+m): 
> > 
> > class Solution { 
> > public: 
> > double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { 
> > 
> > 
> > unsigned long long l = (nums1.size() + nums2.size()) / 2 + 1; 
> > unsigned long long r = (nums1.size() + nums2.size()) % 2; 
> > 
> > unsigned long long n1 = 0; 
> > unsigned long long n2 = 0; 
> > 
> > vector<int> half; 
> > 
> > for(unsigned long long i = 0; i < l; ++i) 
> > { 
> > if(n1 == nums1.size()) 
> > { 
> > half.push_back(nums2[n2]); 
> > ++n2; 
> > } 
> > else if(n2 == nums2.size()) 
> > { 
> > half.push_back(nums1[n1]); 
> > ++n1; 
> > } 
> > else if(nums1[n1] < nums2[n2]) 
> > { 
> > half.push_back(nums1[n1]); 
> > ++n1; 
> > } 
> > else 
> > { 
> > half.push_back(nums2[n2]); 
> > ++n2; 
> > } 
> > } 
> > 
> > if(r) 
> > { 
> > return (double)half.back(); 
> > } 
> > else 
> > { 
> > return ((double)half.back() + (double)half[l - 2]) / 2; 
> > } 
> > 
> > } 
> > }; 
> > 
> > Przemek Biernat
> I jaka uzyskales zlozonosc Twoim zdaniem?

Uzyskałem (m+n) / 2 czyli złożoność liniową.