给出一列互不相同的数,每次比较前两个,把较小的那个放入数列末尾,较大的数视为胜利,执行这样的操作直到某个数胜了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