Problem
Write a function
def solution(A)
that, given an array A consisting of N integers, returns the number of distinct values in array A.
For example, given array A consisting of six elements such that:
A[0] = 2 A[1] = 1 A[2] = 1
A[3] = 2 A[4] = 3 A[5] = 1
the function should return 3, because there are 3 distinct values appearing in array A, namely 1, 2 and 3.
Write an efficient algorithm for the following assumptions:
N is an integer within the range [0..100,000];
each element of array A is an integer within the range [−1,000,000..1,000,000].
Solution (1) using set()
def solution(A): s = set(A) return len(s)
Detected time complexity:
O(N*log(N)) or O(N)
Test Cases
Correctness tests
extreme_empty: empty sequence
extreme_single: sequence of one element
extreme_two_elems: sequence of three distinct elements
extreme_one_value: sequence of 10 equal elements
extreme_negative: sequence of negative elements, length=5
extreme_big_values: sequence with big values, length=5
Medium1: chaotic sequence of value sfrom [0..1K], length=100
Medium2: chaotic sequence of value sfrom [0..1K], length=200
Medium3: chaotic sequence of values from [0..10], length=200
Performance tests
chaotic sequence of values from [0..100K], length=10K
large_random1
chaotic sequence of values from [-1M..1M], length=100K
large_random2
another chaotic sequence of values from [-1M..1M], length=100K
Sol (2) using dict() and then keys().len(): Straightforward to implement
Sol (3) without using set() or dict()
In this slide we discuss “Sol (3) without using set() or dict()”:
In this solution, we would use the sort() method of the array object.
def solution(A): A.sort() rtn = 1 if len(A) == 0: return 0 else: for i in range(1, len(A)): if A[i] != A[i-1]: rtn += 1 return rtn
No comments:
Post a Comment