Cyclic Sort

Time complex O(n) Space complex O(1) key = value

LeetCode 268

眾所周知,輸入數組包含範圍為0到的數字n。我們可以利用這一事實設計一種有效的方法來對數字進行排序。

由於所有數字都是唯一的,因此我們可以嘗試將每個數字放置在正確的位置,例如,將0放置在index處0,將1放置在index處1,依此類推。

一旦將每個數字都放在正確的位置,我們就可以遍歷數組以查找沒有正確數字的索引,而該索引將是我們缺少的數字。

由於數組將具有n數字,這意味著數組索引的範圍是從0到n-1。因此,我們將忽略數字,n因為我們無法將其放置在數組中,所以=>nums[i] < len(nums)

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        start = 0

        while start < len(nums):
            num = nums[start]
            if num < len(nums) and num != start:
                nums[start], nums[num] = nums[num], nums[start]
            else:
                start += 1

        for i in range(len(nums)):
            if nums[i] != i:
                return i

        return len(nums)