input :
- nums
output :
- 양수 중 등장하지 않은 최솟값을 출력하시오.
조건 :
- O(n) time, uses O(1) space
Solution explain : Solution1
idea
- 등장 할 수 있는 원소의 범위를 지정하여 가장 큰 값으로 이를 나타내자.
- 나머지 연산을 통해 해당 값의 위치를, 몫 연산을 통해 등장 횟수를 알 수 있따.
- nums에 값을 2개 추가함으로 0-base 배열에서 0 ~ (max + 1) 까지를 나타내게 한다. - 등장할 수 있는 수의 최대 범위는 max(== length - 1) 까지이다. - max 값을 이용해서 나머지 연산을 한 인덱스 값에다가 max를 더하게 한다면 `원래의 값은 유지, 등장 횟수는 올라감`과 같은 기능을 하게 할 수 있다. - 몫 연산을 통해 1 값이 아닌 것을 찾아 그 인덱스가 등장하지 않았음을 정답으로 주면 된다.
주의
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
nums.append(0)
nums.append(0)
length = len(nums)
for idx in range(length):
if nums[idx] < 0 or nums[idx] >= length - 1:
nums[idx] = 0
for idx in range(length):
# 해당 인덱스 값이 등장했는지는 원소의 나머지 값으로 계산.
nums[nums[idx] % (length - 1)] += length - 1
for idx in range(1, length):
if nums[idx] // (length - 1) == 0:
return idx
