LeetCode - 347.Top K Frequent Elements QuestionEditorial Solution My Submissions

347. Top K Frequent Elements  QuestionEditorial Solution  My Submissions
Total Accepted: 28149
Total Submissions: 63972
Difficulty: Medium
Given a non-empty array of integers, return the k most frequent elements.

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note:
You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

    def topKFrequent(self, nums, k):
        """
        All elements in the nums array can be a candidate of the final outputs. We use the dictionary candidates to count the number of appearance of candidates.
        
        
        """
        count_qualified = 0     # number of qualified candidates
                                # the initial value is obviously 0.
        level = 0               # if candidates[n] > level the n is qualified
                    
        candidates = {}
        
        for n in nums:
            candidates[n] = candidates.get(n,0) + 1  # add 1 to the count
            
            if candidates[n] == level + 1:    

                # this is the only case we care. If candidates[n] <= offset, 

                # then n is not qualified and no impact on the count_effect
                # for candidates[n] > offset + 1, it means that n has been 

                # already counted as qualified. So no impact neither
                count_qualified += 1           # add 1 more qualified candidate 
                
                if count_qualified > k:        

                    # if the number of quanlified candidates is greater than 

                    # the target, we will increase the level of qualification 
                    level += 1
                    for item in candidates.values():# update the count_quanlified
                        if item == level:
                            count_qualified -= 1
        
        
        res = [key for key,val in candidates.items() if val > level]
                        
        return res

One Line Code Challenge: Special Merge

Suppose we have two data frames:

In[29]: df_data
Out[29]: 
   A  B  C  val_0
0  Y  M  1      1
1  Y  F  1      2
2  N  M  1      3
3  N  F  1      4
4  Y  M  2      5
5  Y  F  2      4
6  N  M  2      3
7  N  F  2      2

In[30]: df_rule
Out[30]: 
   A    B   C  val_1
0  Y  NaN NaN    100
1  N    F NaN    200

2  N    M NaN    300

In the context of an ordinary merge on ['A','B','C'], there is no matches because there are NaN in the df_rule.

In the context of a special merge, we allow NaN to be anything. That is to say
(Y,M,1) can match with (Y,M,NaN) (or (Y,NaN,1)etc)

The task is to achieve this special merge.

Solution:
df_rule.groupby(df_rule.apply(lambda x: '-'.join(x[x.notnull()].index.values), axis=1)).apply(lambda df: pd.merge(df, df_data,on=df.dropna(axis=1,how='all').columns.intersection(df_data.columns).tolist(), how='left',suffixes=('_to_remove','')))[df_rule.columns.union(df_data.columns)]

One Line Code Challenge: compute the list of prime factors

factors = lambda n, k=2: ([k] + factors(n / k) if n % k == 0 else factors(n, k+1)) if n > 1 else []


In[17]: factors(3)
Out[17]: [3]
In[18]: factors(4)
Out[18]: [2, 2]
In[19]: factors(9)
Out[19]: [3, 3]
In[20]: factors(18)
Out[20]: [2, 3, 3]
In[21]: factors(24)
Out[21]: [2, 2, 2, 3]
In[22]: factors(1)
Out[22]: []