merge sorted array
unknown
c_cpp
16 days ago
1.2 kB
4
Indexable
Never
complexity time : o(n+m) complexity Space : o(1) class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { int i = m - 1, j = n - 1, k = m + n - 1; while(i >= 0 && j >= 0) { if(nums1[i]>nums2[j]) { nums1[k--]=nums1[i--]; } else { nums1[k--]=nums2[j--]; } } while(j>=0) { nums1[k--] = nums2[j--]; } } }; _______________________________________________ complexity time o(mLog(m)+nlog(n+m)) complexity space : o(n+m) using ordered map : class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { map<int,int> sorted_map; for(int i = 0; i < m; i++) { sorted_map[nums1[i]]++; } for(int i =0;i<n;i++) { sorted_map[nums2[i]]++; } nums1.clear(); for(auto itr = sorted_map.begin(); itr != sorted_map.end() ; ++itr) { while(itr->second--) { nums1.push_back(itr->first); } } } };
Leave a Comment