Why this is a hard question?


  • -31
    H

    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
    F

    HashSet cost O(n) space.


  • 0

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


  • 0
    S

    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
    L

    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
    K

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


  • 0
    W

    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.