My solution using C++ STL libraries


  • 0
    S

    I used a binary tree tally(std::map<int, int>) and another dynamic array to merge the two array in an ordered manner, and this could work with numbers in any order.

    I then performed median calculation. The end.

    Clearly I do not have a algorithm frame of mind and I just did bullshit.
    Despise me if you want, I'm not a algorithmist, I just want to show how broken OJ really is.

    class Solution {
    public:
      double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        map<int, int> tally;
        vector<int> arr;
        const int j = nums1.size() + nums2.size();
        arr.reserve(j);
        for (auto &x : nums1) tally[x]++;
        for (auto &x : nums2) tally[x]++;
        for (auto &it : tally) arr.insert(arr.end(), it.second, it.first);
    
        return (arr[(j - 1) / 2] + arr[j / 2]) * 0.5;
      }
    };
    

    If I'm correct about the time complexity it should be O(log(mn)) O(m+n) and the space complexity is ~O(m+n)~O(2*(m+n))


  • 0

    @stevefan1999 said in My solution using C++ STL libraries:

    I just want to show how broken OJ really is.

    Then why don't you?


  • 0
    S

    @ManuelP Yes, you're right. I should just assign a super big array and do all that sorting.

    int arr[10000];
    class Solution {
    public:
      double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        const int i = nums1.size() + nums2.size();
        copy(nums1.begin(), nums1.end(), arr);
        copy(nums2.begin(), nums2.end(), arr + nums1.size());
    
        sort(arr, arr + i);
    
        const auto ret = (arr[(i - 1) / 2] + arr[i / 2]) * 0.5;
        memset(arr, 0, i * sizeof(int));
        return ret;
      }
    };
    

    Oh so all the time it was just a O(n log n) algorithm...with O(m+n) space complexity...


  • 0

    Sorry, I don't know what that's supposed to achieve...


  • 0
    S

    @ManuelP I was trying to be an ass


Log in to reply
 

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