diff options
author | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
---|---|---|
committer | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
commit | d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch) | |
tree | 96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /first_missing_positive.py | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'first_missing_positive.py')
-rw-r--r-- | first_missing_positive.py | 33 |
1 files changed, 33 insertions, 0 deletions
diff --git a/first_missing_positive.py b/first_missing_positive.py new file mode 100644 index 0000000..8166acf --- /dev/null +++ b/first_missing_positive.py @@ -0,0 +1,33 @@ +# 41. First Missing Positive + +""" +given an unsorted integer array 'nums', return the smallest missing positive +number. you must implement an algorithm that runs in O(n) time and uses O(1) +auxiliary space. +""" + + +class Solution(object): + def firstMissingPositive(self, nums): + """ + :type nums: List[int] + :rtype: int + """ + nums.append(0) + n = len(nums) + for i in range(len(nums)): + if nums[i] < 0 or nums[i] >= n: + nums[i] = 0 + for i in range(len(nums)): + nums[nums[i] % n] += n + for i in range(1, len(nums)): + if nums[i] / n == 0: + return i + return n + + +if __name__ == "__main__": + obj = Solution() + print(obj.firstMissingPositive([1, 2, 0])) + print(obj.firstMissingPositive([3, 4, -1, 1])) + print(obj.firstMissingPositive([7, 8, 9, 11, 12])) |