09-19 leetcode-0287

题目

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and uses only constant extra space.

题解

这题第一种做法就是经典的 bitmap，空间复杂度 O1

class Solution:
    def findDuplicate(self, nums: list[int]) -> int:
        mask = 0
        for num in nums:
            if mask & (1 << num):
                return num
            else:
                mask |= 1 << num
        return -1

第二种做法是原地数组修改

class Solution:
    def findDuplicate(self, nums: list[int]) -> int:
        for item in nums:
            index = abs(item) - 1
            if nums[index] < 0:
                return index + 1
            else:
                nums[index] = -nums[index]

Comments