動機

資料本身也是有特性的

Problem

Given an unsorted integer array nums, return the smallest missing positive integer.

You must implement an algorithm that runs in O(n) time and uses constant extra space.

 

Example 1:

Input: nums = [1,2,0]Output: 3

Example 2:

Input: nums = [3,4,-1,1]Output: 2

Example 3:

Input: nums = [7,8,9,11,12]Output: 1

 

Constraints:

  • 1 <= nums.length <= 5 * 105
  • -231 <= nums[i] <= 231 - 1

Sol

從array中找出沒有的最小的正整數

同時要求時間是O(n)，空間是常數

如果不管空間，就是用hash，走兩次就ok了

但現在不能用hash，又要類似排序的效果，這時就只能看有沒有辦法把每筆資料定位

注意到array的index一定是正整數，又可以一一對應，i對到i+1

所以接下來的任務就是讓每個i盡量是i+1。

那麼要從i+1到最後一個去找嗎? 這樣會變成O(n^2)!!

如果資料是在範圍內的，就一定只有那個位置可以擺，所以就是根據資料把資料換到正確的位置，反覆換下去，直到合法或是無法再換了

這個過程讓我想到，seasoned schemer的scramble，與little mler的exception的例子

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        if not nums:
            return 1
        for i in range(0,len(nums)):
            while (nums[i] > 0 and nums[i] <= len(nums)) and nums[i] != nums[nums[i]-1]:
                tmp = nums[nums[i]-1]
                nums[nums[i]-1] = nums[i]
                nums[i] = tmp
        for i in range(0,len(nums)):
            if i+1 != nums[i]:
                return i+1
        return len(nums)+1