C++ O(n)time O(n)space using bucket sort, yet O(n)space


  • 0
    X

    Using an array as bucket[n+1]={0,0...,0}, number from vecter<int> as index to bucket, count frequency of numbers from vector, if frequency=bucket[num[i]] > 1, then we find duplicate.
    ennnn, yet, is this O(1) space? or O(2n) space?
    Ed: Thanks @Misaka-10032 point out, it should be O(n)space.

    class Solution {
    public:
        int findDuplicate(vector<int>& nums) {
            int sz = nums.size(); 
            if(sz < 2) return 0; 
            
            int bucket[sz+1] = {0};
            for(int i = 0; i < sz; i++){
                if(++bucket[nums[i]] > 1) 
                    return nums[i];
            }
            return 0; // in case of NO duplicates
        }
    };
    

  • 0

    No, it's not.


  • 0
    X

    @Misaka-10032 thanks Misaka, it should be o(n)space, i will change.


Log in to reply
 

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