LeetCode 645: Set Mismatch

link

Cyclic sort

Cyclic sort to match nums with the reference sequence \langle 1, 2, 3, \ldots, n \rangle. The first mismatch is the answer.

Time: \mathcal{O}(n), space: \mathcal{O}(1).

class Solution:
    def cyclic_sort(self, nums: List[int], begin: int, end: int, offset: int) -> None:
        for i in range(begin, end):
            while (
                nums[i] != i - begin + offset
                and (j := begin + nums[i] - offset) < end
                and nums[i] != nums[j]
            ):
                nums[i], nums[j] = nums[j], nums[i]

    def find_first_mismatch(
        self, nums: List[int], begin: int, end: int, offset: int
    ) -> Tuple[int, int]:
        for i in range(begin, end):
            if (expected := i - begin + offset) != nums[i]:
                return expected, nums[i]
        return end - begin + offset, None

    def findErrorNums(self, nums: List[int]) -> List[int]:
        begin, end, offset = 0, len(nums), 1
        self.cyclic_sort(nums, begin, end, offset)
        miss, dup = self.find_first_mismatch(nums, begin, end, offset)
        return [dup, miss]

Leave a comment