Bitmap simulation with high performance


  • 0
    L

    Most solutions are using Binary-Search, I tried another way to achieve the goal. Though more space is used (n / 8), however it gets the high performance. Just an unconventional way, :-)

    class Solution(object):
        def findDuplicate(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            flagNums = [0] * ((len(nums) >> 3) + (1 if len(nums) & 7 else 0))
            
            for n in nums:
                i = 1 << (n & 7) - 1 if n & 7 else 1 << 7
                if flagNums[n >> 3] & i:
                    return n
                else:
                    flagNums[n >> 3] ^= i
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.