PAT 1144 The Missing Number python解法
2437 ワード
1144 The Missing Number(20分)Given N integers,you are supposed to find the smallest positive integer that is NOT in the given list.
Input Specification: Each input file contains one test case. For each case, the first line gives a positive integer N (≤105 ). Then N integers are given in the next line, separated by spaces. All the numbers are in the range of int.
Output Specification: Print in a line the smallest positive integer that is missing from the input list.
Sample Input: 10 5 -25 9 6 1 3 4 2 5 17 Sample Output: 7
題意:N個の数を与え、リストにない最小正の整数を探し出す.
解題の考え方:暴力解法1.入力した数をコレクションsに格納し、再実行するとタイムアウトし、pythonでのオペレーションセットの効率はオペレーションリストよりも高くなります.2.1からタイトルに与える最大値105+2(プラス2の原因は最大で1-105のすべての数がある可能性があるので、最後に集合の中で最小でない数は105+1)まで、集合sの中でない最初の数を探し出して求めます.注意:1がコレクションにない場合、出力は1です.
Input Specification: Each input file contains one test case. For each case, the first line gives a positive integer N (≤105 ). Then N integers are given in the next line, separated by spaces. All the numbers are in the range of int.
Output Specification: Print in a line the smallest positive integer that is missing from the input list.
Sample Input: 10 5 -25 9 6 1 3 4 2 5 17 Sample Output: 7
題意:N個の数を与え、リストにない最小正の整数を探し出す.
解題の考え方:暴力解法1.入力した数をコレクションsに格納し、再実行するとタイムアウトし、pythonでのオペレーションセットの効率はオペレーションリストよりも高くなります.2.1からタイトルに与える最大値105+2(プラス2の原因は最大で1-105のすべての数がある可能性があるので、最後に集合の中で最小でない数は105+1)まで、集合sの中でない最初の数を探し出して求めます.注意:1がコレクションにない場合、出力は1です.
n = int(input())
s = set(input().split())
#n = 10
#l = [5, -25, 9, 6, 1, 3, 4, 2, 5, 17]
for i in range(1, 100002):
if str(i) not in s:
print(i)
break