Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给出一列互不相同的数,每次比较前两个,把较小的那个放入数列末尾,较大的数视为胜利,执行这样的操作直到某个数胜了k次,输出该数。只要模拟完整个队列走完一遍或者某个数已达k次。


#1535
#
Runtime: 491 ms (Beats 40%)
#
Memory: 23.8 MB (Beats 13.33%)

class Solution(object):
    def getWinner(self, arr, k):
        """
        :type arr: List[int]
        :type k: int
        :rtype: int
        
"""
        cnt = defaultdict(int)
        n = len(arr)
        mx = arr[0]
        for i in xrange(1, n):
            mx = max(mx, arr[i])
            cnt[mx] += 1
            if cnt[mx] >= k:
                return mx
        return mx

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理