Codility每周一课：L8 Leader(8.2)

8.png

P8.2 Dominator

Find an index of an array such that its value occurs at more than half of indices in the array.

• P8.2 支配数
  返回数组中支配数的索引

由N个整数组成的数组A。数组A的支配数是出现次数为A的元素个数一半以上的数。

例如，考虑数组A：
A[0]=3，A[1]=4，A[2]=3，A[3]=2，A[4]=3，A[5]=-1，A[6]=3，A[7]=3。
A的支配数是3，因为它出现在A的8个元素中的5个元素中（即索引为0、2、4、6和7），而5是8的一半以上。

编写函数:

def solution(A)

给定一个由N个整数组成的数组A，则返回数组A的支配数的任何索引。如果数组A没有支配数，则函数应返回−1。

例如，针对上面的示例，函数可以返回0、2、4、6和7中的任何一个数。

假定：

1. N是区间[0，100000]内的整数；

2 .数组A的每个元素都是区间[-2147483648，2147483647]内的整数；

• 解题思路

首先遍历数组，获得所有元素的出现次数，用字典存储。然后判断次数最大的是否超过数组元素个数的一半。如果没有返回-1，如果存在则利用A.index()返回索引。

• Python3代码

# -*- coding：utf-8 -*-
# &Author  AnFany
# Lesson 8：Leader
# P 8.2 Dominator


def solution(A):
    """
    判断数组A是否存在支配数，存在返回其任何一个索引，否再返回-1
    :param A: 数组
    :return: 返回支配数的任何索引，或者-1
    """
    if len(A) == 0:
        return -1
    leader_dict = {}
    for i in A:
        if i in leader_dict:
            leader_dict[i] += 1
        else:
            leader_dict[i] = 1

    leader, times = max(leader_dict.items(), key=lambda x: x[1])

    if times > len(A) / 2:
        return A.index(leader)
    else:
        return -1

• 结果
  image
  点击获得更多编程练习题。欢迎Follow，感谢Star!!! 扫描关注微信公众号pythonfan，获取更多。

image image