leetcode刷题记录8

介绍

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.

思路

没啥好说的，很简单，做两次排序就可以了，中间出了一个bug，没考虑到传入的数列只有一个数的情况，还有最后一个数不会计入n，所以在首尾分别加个字符就行了。首尾容易出问题就让他不成为首尾就行了

代码

class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        nums.sort()
        nums=['a']+nums+['b']
        mark=''
        n=0
        s=[]
        
        for i in nums:
            if mark!=i:
                s.append([n,mark])
                mark=i
                n=1
            else:
                n=n+1
        del s[:2]
        s.sort(reverse=True)
        s=s[:k]
        for i in range(k):
            s[i]=s[i][1]
        return s