Python / наименьшее положительное целое число - PullRequest
Новая
       33

Python / наименьшее положительное целое число

0 голосов
/ 08 марта 2020

Я взял следующую демонстрационную задачу codility. Напишите функцию:

def solution (A)

, которая, учитывая массив A из N целых чисел, возвращает наименьшее положительное целое число (больше 0) что не встречается в A.

Например, если A = [1, 3, 6, 4, 1, 2], функция должна вернуть 5.

При условии A = [1 , 2, 3], функция должна возвращать 4.

Учитывая A = [−1, −3], функция должна возвращать 1.

Напишите эффективный алгоритм для следующих предположений:

N - целое число в диапазоне [1..100,000]; каждый элемент массива A является целым числом в диапазоне [−1 000 000..1 000 000].

Мое решение 

def solution(A):
    # write your code in Python 3.6
    l = len(A)
    B = []
    result = 0
    n = 0
    for i in range(l):
        if A[i] >=1:
            B.append(A[i]) 
    if B ==[]:
        return(1)
    else:    
       B.sort() 
       B = list(dict.fromkeys(B))
       n = len(B)
       for j in range(n-1):
           if B[j+1]>B[j]+1:
                result = (B[j]+1)
       if result != 0:
            return(result)
       else:
            return(B[n-1]+1)

Хотя я получаю правильный вывод для всех входных данных, которые я пробовал, но мой результат был всего 22%. Может ли кто-нибудь выделить, где я иду не так

Ответы [ 2 ]

0 голосов
/ 08 марта 2020

Я думаю, что это должно быть так же просто, как начать с 1 и проверить, какое число сначала не появляется. 

def solution(A):
    i = 1
    while i in A:
        i += 1

    return i

Вы также можете рассмотреть возможность размещения элементов A в наборе (для повышения производительности при поиске) , но я не уверен, что оно подходит для этого случая.

Обновление: Я проводил некоторые тесты с числами, которые дал ОП (числа от отрицательного миллиона до положительного миллиона и 100000 элементы). 

100000 elements:
Linear Search: 0.003s
Set Search: 0.017s

1000000 elements (extra test):
Linear Search: 0.8s
Set Search: 2.58s
0 голосов
/ 08 марта 2020

Попробуйте, я предполагаю, что список не отсортирован, но если он отсортирован, вы можете удалить number_list = sorted(number_list), чтобы сделать его немного быстрее. 

def get_smallest_positive_integer(number_list):
    if all(number < 0 for number in number_list) or 1 not in number_list:
        #checks if numbers in list are all negative integers or if 1 is not in list
        return 1
    else:
        try:
            #get the smallest number in missing integers
            number_list = sorted(number_list) # remove if list is already sorted by default
            return min(x for x in range(number_list[0], number_list[-1] + 1) if x not in number_list and x != 0)
        except:
            #if there is no missing number in list get largest number + 1
            return max(number_list) + 1


print(get_smallest_positive_integer(number_list))

input: 

number_list = [1,2,3]

Выход: 

>>4

Вход: 

number_list = [-1,-2,-3]

Выход: 

>>1

Вход: 

number_list = [2]

Выход: 

>>1

вход: 

number_list = [12,1,23,3,4,5,61,7,8,9,11]

выход: 

>>2

вход: 

number_list = [-1,3,2,1]

выход: 

>>4
...