Cyclic sort
Cyclic sort to match nums with the reference sequence . The first mismatch is the answer.
Time: , space:
.
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