Why this is a hard question?

  • -31

    Use HashSet, it cost O(1) space.

    Then loop the numbers
    If it's in the set, return that number;
    else, add it into the set.

    My Java code takes only 8ms to complete all the test cases.

    It should be a simple question.

  • 0

    HashSet cost O(n) space.

  • 0

    Did you really understand this problem?
    The following is the request for this Alogrithm:
    You must use only constant, O(1) extra space.

  • 0

    From other aspect, he may be right. Say if we create a bitmap whose length is 2^64-1(constant, O(1) space with respect to n), and use it as a hashmap...

  • -1

    From mathematical perspective, the space complexity of such solution increases linearly as the length of the array grows, no matter what space unit it is - 1 bit or 8 byte.

  • 0

    I think you should understand the space complex of HashSet is O(n).

  • 0

    Do you think the bitmap need O(n) space? We need to represent the nums from 1 to n.Although the bit map could reduce the space we use , it remains O(n).

Log in to reply

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