Share my fastest 40ms c++ solution


  • 2
    T
    public:   
     double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
                const int size_1 = nums1.size();
                const int size_2 = nums2.size();
                int k = (size_1 + size_2) / 2;
                int res1 = find_kth_in_two_sorted_arrays(nums1,nums2, k+1);
                if ((size_1 + size_2) % 2 == 0) {
                    int res2 = find_kth_in_two_sorted_arrays(nums1,nums2, k);
                    return ( (double) res1 + res2) / 2.0;
                }
                return res1;
            }
        private:
            double find_kth_in_two_sorted_arrays (const vector <int >& A, const vector <int >& B, int k){
                int b = max(0, static_cast <int >(k - B.size ()));
                int t = min(static_cast <int >(A.size ()), k);
                while(b < t){
                    int x = b + ((t - b) >> 1);
                    int A_x_1 = (x <= 0 ? INT_MIN : A[x - 1]);
                    int A_x = (x >= A.size () ? INT_MAX : A[x]);
                    int B_k_x_1 = (k - x <= 0 ? INT_MIN  : B[k - x - 1]);
                    int B_k_x = (k - x >= B.size () ? INT_MAX: B[k - x]);
                    
                    if (A_x < B_k_x_1){
                        b = x+1;
                    }
                    else if (A_x_1 > B_k_x) {
                        t = x-1;
                    }
                    else
                        return max(A_x_1 , B_k_x_1);
                    
                }
                int A_b_1 = b <= 0 ? INT_MIN: A[b - 1];
                int B_k_b_1 = k - b - 1 < 0 ? INT_MIN : B[k - b - 1];
                return max(A_b_1 , B_k_b_1);
        
            }

  • 0
    A

    Thanks for sharing. But it seems hard to read. What do b, t, k mean?


Log in to reply
 

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