human
I am working on the file "01_Sort.ipynb".
The first task is:
Top K Frequent Elements

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.
Show Company Tags
Show Tags
Show Similar Problems
Can you write Python code for it?

Can you provide a the Python code you requested?
assistant
#Here is the Python code you requested.

class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        dic, ans = {}, []
        for i in range(len(nums)):
            dic[nums[i]] = dic.get(nums[i], 0) + 1
        for num in dic:
            if len(ans) == 0 or dic[num] <= dic[ans[-1]]:
                ans.append(num)
            elif dic[num] >= dic[ans[0]]:
                ans = [num] + ans
            else:
                l, r = 0, len(ans)-1
                while l < r:
                    m = (l+r)/2
                    if dic[ans[m]] >= dic[num]:
                        l = m + 1
                    else:
                        r = m - 1
                if dic[ans[l]] >= dic[num]:
                    ans = ans[:l+1] + [num] + ans[l+1:]
                else:
                    ans = ans[:l] + [num] + ans[l:]
            if len(ans) > k:
                ans.pop()
        return ans