Time O(N+2) C#


  • 0

    This is a tricky solution without considering bit manipulation, implement a set, if we meet the element A, add into set, if we meet element A again, remove A from set.
    Loop the whole array and the set would only contain the elements only appear once.
    Since the duplicate value is two. So it's easier to go this way.(which means, if the interviewer modified to duplicate values to odd times, like 3/5/7, this method is invalid)
    And the result would always to be 2(Again, related to space requirement)
    So in time complexity:
    1 pass array use N time, set insert/delete only take O(1) time. -> O(N)
    loop through 2 elements set to add to ouput array. O(2) -> total time: O(N+2)

    And worst space is O(N/2) =>O(N).

        //Tine(N + 2) Space(N)
        public int[] SingleNumber(int[] nums) {
            var set = new HashSet<int>(); 
            
            for(int i= 0; i< nums.Length; i++)
            {
                if(!set.Contains(nums[i]))
                   set.Add(nums[i]);
                else
                   set.Remove(nums[i]);
            }
            
            int[] res = new int[set.Count];  
            
            int j = 0;
            foreach(int val in set)
            {
                res[j++] = val;
            }
            return res;
        }
    

Log in to reply
 

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