Skip to main content

LeetCode Algorithm Questions by Python

4. Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays.
Example 1:
nums1 = [1, 3]
nums2 = [2]

The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

The idea is to pick up the numbers in nums2 that are smaller than a number in nums1, until we get the median.

Pay attention:
1. consider three cases: odd, even, and null;
2. max of nums1 may smaller than min of nums2;
3. use float() while doing the division.

My code in Python is as follows:

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        m = len(nums1)
        n = len(nums2)
        mn = m + n
        i = 0
        acc = 0
        med2 = 0
        if m == 0 or n == 0:
            nums1.extend(nums2)
            if mn % 2 == 0:
                return float(nums1[(mn/2-1)]+nums1[mn/2])/2
            else:
                return nums1[(mn+1)/2-1]
        elif mn % 2 == 0:
            p = mn/2+1
            for n1 in nums1:
                while i < n and nums2[i] < n1:
                    med1 = med2
                    med2 = nums2[i]
                    i += 1
                    acc += 1
                    if acc == p:
                        return float(med1+med2)/2
                        break
                med1 = med2
                med2 = n1
                acc += 1
                if acc == p:
                    return float(med1+med2)/2
                    break
            if acc == p-1:
                return float(med2+nums2[acc-m])/2
            elif acc < p-1:
                return float(nums2[p-m-2]+nums2[p-m-1])/2
        else:
            p = (mn+1)/2
            for n1 in nums1:
                while i < n and nums2[i] < n1:
                    med1 = med2
                    med2 = nums2[i]
                    i += 1
                    acc += 1
                    if acc == p:
                        return med2
                        break
                med1 = med2
                med2 = n1
                acc += 1
                if acc == p:
                    return med2
                    break
            if acc < p:
                return nums2[p-m-1]
               




Labels:

Comments

Post a Comment

Popular posts from this blog

Weighted Percentile in Python Pandas

Unfortunately, there is no weighted built-in functions in Python. If we want to get some weighted percentiles by Python, one possible method is to extend the list of data, letting the values of weight as the numbers of elements, which is discussed in a Stack Overflow poster . For example, if we have a data like, score   weight 5          2 4          3 2          4 8          1 we firstly extend the list of scores to {5, 5, 4, 4, 4, 2, 2, 2, 2, 8}, and then find the percentiles such as 10% or 50% percentile. The limitations of this method are, (1) weight must be integers; (2) values of weight cannot be very large. What if we want to calculate the weighted percentiles of a large dataset with very large non-integer weights? In this article, I want to show you an alternative method, under Python pandas. step1: given percentile q, (0<=q<=1), calculate p = q * sum of wei...
2 comments
Read more

Rcpp Example: Partition Based Selection Algorithm

In this post, I'm going to take a Rcpp example that call a C++ function to find kth smallest element from an array. A partition-based selection algorithm could be used for implementation. A most basic partition-based selection algorithm, quickselect , is able to achieve linear performance to find the kth element in an unordered list. Quickselect is a variant of quicksort , both of which choose a pivot and then partitions the data by it. The procedure of quickselect is to firstly move all elements smaller than the pivot to the left and what greater than the pivot the the right by exchanging the location of them, given a pivot such as the last element in the list; and then to move the elements in the left or right sublist again according to a new pivot until getting exact kth elements. The difference from quicksort is that quickselect only need to recurses on one side where the desired kth element is, instead of recursing on both sides of the partition which is what quicksort ...
Post a Comment
Read more

Trend Removal Using the Hodrick-Prescott (HP) Filter

Hodrick-Prescott filter (see Hodrick and Prescott (1997)) is a popular tool in macroeconomics for fitting smooth trend to time series. In SAS, we can use PROC UCM to realize the HP filter.  The dataset considered in this example consists of quarterly real GDP for the United States from 1947-2016  (b illions of chained 2009 dollars ,  seasonally adjusted annual rate ). The data can be download from this link  https://fred.stlouisfed.org/series/GDPC1   %macro hp(input= ,date= ,int= ,var= ,par= ,out= ); proc ucm data=&input; id &date interval=&int; model &var; irregular plot=smooth; level var= 0 noest plot=smooth; slope var=&par noest; estimate PROFILE; forecast plot=(decomp) outfor=&out; run; %mend ; % hp (input=gdp,date=year,int=qtr,var=gdp,par= 0.000625 ,out=result); I use SAS MACROS to define a function for HP filter. "input" is the data file you use, "date" is the variable for time, "int...
3 comments
Read more