Codility每周一课：L6 Sorting(P6.1)

0.png

P6.1 Distinct

Compute number of distinct values in an array.

• P6.1 不同值
  计算一个数组中不同值的个数

编写函数

def solution(A)

给定一个由N个整数组成的数组A，则返回数组A中不同值的数目。

例如，给定的数组A由六个元素组成： A[0]=2, A[1]=1, A[2]=1, A[3]=2, A[4]=3, A[5]=1 函数应该返回3，因为数组A中有3个不同的值，即1、2和3。

假定：

1. N是区间[0，100000]内的整数；
2. 数组A的每个元素都是区间[-1000000，1000000]内的整数。

• 解题思路

利用Python函数set或者利用字典。

• Python3代码

# -*- coding：utf-8 -*-
# &Author  AnFany
# Lesson 6：Sorting
# P 6.1 Distinct


def solution_one(A):
    """
    返回数组A中不同数值的个数，时间复杂度O(N*log(N)) or O(N)，利用Python函数set
    :param A: 整数数组
    :return: 不同值的个数
    """
    return len(set(A))


def solution(A):
    """
    返回数组A中不同数值的个数，时间复杂度O(N*log(N)) or O(N)，利用字典
    :param A: 整数数组
    :return: 不同值的个数
    """
    number_dict = {}
    sign = 0
    for j in A:
        if j not in number_dict:
            number_dict[j] = 0
            sign += 1
    return sign

• 结果

0.png

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

image image